Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <map>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <iomanip>
- #include <math.h>
- #include <limits.h>
- using namespace std;
- typedef long long int ll;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vint;
- int n, q;
- vint degrees;
- vector<bool> can;
- void add(int x) {
- //cerr << "add " << x << endl;
- vint nvec = degrees;
- for (int i = 0; i <= n; i++) {
- if (degrees[i] && i + x <= n) {
- nvec[i + x]++;
- can[i + x] = true;
- }
- }
- /*cerr << "nvec: ";
- for (auto it : nvec)
- cerr << it << " ";
- cerr << endl;*/
- degrees = nvec;
- }
- void remove(int x) {
- //cerr << "remove " << x << endl;
- vint nvec = degrees;
- for (int i = 0; i <= n; i++) {
- if (nvec[i] && i + x <= n)
- nvec[i + x]--;
- }
- /*cerr << "nvec: ";
- for (auto it : nvec)
- cerr << it << " ";
- cerr << endl;*/
- degrees = nvec;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cin >> n >> q;
- vector<pii> vec;
- for (int i = 0; i < q; i++) {
- int l, r, x;
- cin >> l >> r >> x;
- l--; r--;
- vec.push_back({l, x});
- vec.push_back({r + 1, -x});
- }
- sort(vec.begin(), vec.end());
- degrees.resize(n + 1);
- can.resize(n + 1);
- degrees[0] = 1;
- for (auto it : vec) {
- if (it.second < 0)
- remove(-it.second);
- else
- add(it.second);
- }
- vint res;
- for (int i = 1; i <= n; i++) {
- if (can[i]) {
- res.push_back(i);
- }
- }
- cout << res.size() << endl;
- for (auto it : res)
- cout << it << " ";
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement