Codeforces981E

63 阅读 0 评论 42 点赞

我是靠谱客的博主超帅芹菜，最近开发中收集的这篇文章主要介绍Codeforces981E，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接:

http://codeforces.com/contest/981/problem/E

题意:

给出若干个操作，问任意选出这些操作的子集，最大值的在1-n的有多少种可能。

题解：

那就是我其实只需要最后去看一下能否凑成即可不需要考虑是否是最大因为在选择的时候我们可以任选子集可以尝试好一个数通过好多次加法之后他不是最大的那么一定构造不出。直接在线段树是跑bitset即可，复杂度(N*LogN*N/64);

E. Addition on Segments

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Grisha come to a contest and faced the following problem.

You are given an array of size $n$ , initially consisting of zeros. The elements of the array are enumerated from $1$ to $n$ . You perform $q$ operations on the array. The $i$ -th operation is described with three integers $l_{i}$ , $r_{i}$ and $x_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq n$ , $1 \leq x_{i} \leq n$ ) and means that you should add $x_{i}$ to each of the elements with indices $l_{i}, l_{i} + 1, \dots, r_{i}$ . After all operations you should find the maximum in the array.

Grisha is clever, so he solved the problem quickly.

However something went wrong inside his head and now he thinks of the following question: "consider we applied some subset of the operations to the array. What are the possible values of the maximum in the array?"

Help Grisha, find all integers $y$ between $1$ and $n$ such that if you apply some subset (possibly empty) of the operations, then the maximum in the array becomes equal to $y$ .

Input

The first line contains two integers $n$ and $q$ ( $1 \leq n, q \leq 10^{4}$ ) — the length of the array and the number of queries in the initial problem.

The following $q$ lines contain queries, one per line. The $i$ -th of these lines contains three integers $l_{i}$ , $r_{i}$ and $x_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq n$ , $1 \leq x_{i} \leq n$ ), denoting a query of adding $x_{i}$ to the segment from $l_{i}$ -th to $r_{i}$ -th elements of the array, inclusive.

Output

In the first line print the only integer $k$ , denoting the number of integers from $1$ to $n$ , inclusive, that can be equal to the maximum in the array after applying some subset (possibly empty) of the given operations.

In the next line print these $k$ integers from $1$ to $n$ — the possible values of the maximum. Print these integers in increasing order.

Examples

Input

Copy

Output

Copy

4
1 2 3 4

Input

Copy

7 2
1 5 1
3 7 2

Output

Copy

3
1 2 3

Input

Copy

Output

Copy

6
2 3 5 6 8 9

Note

Consider the first example. If you consider the subset only of the first query, the maximum is equal to $1$ . If you take only the second query, the maximum equals to $2$ . If you take the first two queries, the maximum becomes $3$ . If you take only the fourth query, the maximum becomes $4$ . If you take the fourth query and something more, the maximum becomes greater that $n$ , so you shouldn't print it.

In the second example you can take the first query to obtain $1$ . You can take only the second query to obtain $2$ . You can take all queries to obtain $3$ .

In the third example you can obtain the following maximums:

You can achieve the maximim of $2$ by using queries: $(1)$ .
You can achieve the maximim of $3$ by using queries: $(2)$ .
You can achieve the maximim of $5$ by using queries: $(1, 2)$ .
You can achieve the maximim of $6$ by using queries: $(3)$ .
You can achieve the maximim of $8$ by using queries: $(1, 3)$ .
You can achieve the maximim of $9$ by using queries: $(2, 3)$ .

#include <bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn = 1e4+7;
vector<int>V[maxn<<2];
bitset<maxn> ans;
void update(int d, int L, int R, int l, int r, int rt)
{
if(L <= l && r <= R) {
V[rt].push_back(d);
return ;
}
int mid = (l + r) / 2;
if(L <= mid) update(d, L, R, lson);
if(R > mid) update(d, L, R, rson);
}
void query(bitset<maxn>b, int l, int r, int rt)
{
for(auto it : V[rt]) b |= (b << it);
if(l == r) {
ans |= b;
return;
}
int mid = (l + r) / 2;
query(b, lson);
query(b, rson);
}
int main()
{
int n, q;
scanf("%d %d", &n, &q);
for(int i = 1;i <= q;i ++) {
int l, r, d;
scanf("%d %d %d", &l, &r, &d);
update(d,l,r,1,n,1);
}
bitset<maxn>b;
b[0] = 1;
query(b, 1, n, 1);
vector<int> res;
for(int i = 1;i <= n;i ++) {
if(ans[i]) res.push_back(i);
}
int sz = res.size();
printf("%dn", sz);
for(int i = 0;i < sz;i ++) {
if(i > 0) printf(" %d", res[i]);
else printf("%d",res[i]);
}
puts("");
return 0;
}