#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
void print(long double t) {cerr << t;}
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
long long ka() {
long long x = 0;
bool z = false;
while (1)
{
char y = getchar();
if (y == '-')
z = true;
else if ('0' <= y && y <= '9')
x = x * 10 + y - '0';
else
{
if (z)
x *= -1;
return x;
}
}
}
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
fastIO();
if (str != "") {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 250005;
long long n, m, q;
vector<pair<long long, pair<long long, long long>>> to_add[N], to_del[N], qq[N];
vector<pair<long long, pair<long long, long long>>> to_add2[N], to_del2[N];
deque<pair<long long, pair<long long, long long>>> st[N];
long long cnt[N];
struct node {
long long type;
long long l, r, k, c;
};
vector<node> queries;
struct segTree {
struct node {
long long value, cur, lazy;
};
int size = 1;
vector<node> tree;
void init(int s) {
while(s > size) {
size *= 2;
}
tree.assign(2 * size - 1, {0, 0, 0});
}
void propagate(int x, int lx, int rx) {
if(rx - lx == 1 || !tree[x].lazy) {
return;
}
int mid = (lx + rx) / 2;
tree[2 * x + 1].value += tree[x].lazy * (mid - lx);
tree[2 * x + 1].lazy += tree[x].lazy;
tree[2 * x + 2].value += tree[x].lazy * (rx - mid);
tree[2 * x + 2].lazy += tree[x].lazy;
tree[x].lazy = 0;
}
void upd(int l, int r, long long value, long long vul, int x, int lx, int rx) {
propagate(x, lx, rx);
if(lx >= r || rx <= l) {
return;
}
if(lx >= l && rx <= r) {
if(value == -1) {
tree[x].value = 0;
tree[x].cur = 0;
tree[x].lazy = 0;
} else {
tree[x] = {value, vul, value};
propagate(x, lx, rx);
}
return;
}
int mid = (lx + rx) / 2;
upd(l, r, value, vul, 2 * x + 1, lx, mid);
upd(l, r, value, vul, 2 * x + 2, mid, rx);
tree[x].value = tree[2 * x + 1].value + tree[2 * x + 2].value;
}
void upd(int l, int r, long long value, long long vul) {
upd(l, r, value, vul, 0, 0, size);
}
pair<long long, long long> qry(long long d, int x, int lx, int rx) {
propagate(x, lx, rx);
if(rx - lx == 1) {
return {tree[x].cur, lx};
}
int mid = (lx + rx) / 2;
if(tree[2 * x + 1].value >= d) {
return qry(d, 2 * x + 1, lx, mid);
} else {
return qry(d - tree[2 * x + 1].value, 2 * x + 2, mid, rx);
}
}
pair<long long, long long> qry(long long d) {
if(tree[0].value < d) {
return {0ll, 0ll};
}
return qry(d, 0, 0, size);
}
};
segTree seg;
struct segTreeSum {
struct node {
long long value, lazy;
};
int size = 1;
vector<node> tree;
void init(int s) {
while(s > size) {
size *= 2;
}
tree.assign(2 * size - 1, {0, 0});
}
void propagate(int x, int lx, int rx) {
if(rx - lx == 1 || !tree[x].lazy) {
return;
}
int mid = (lx + rx) / 2;
tree[2 * x + 1].value += tree[x].lazy * (mid - lx);
tree[2 * x + 1].lazy += tree[x].lazy;
tree[2 * x + 2].value += tree[x].lazy * (rx - mid);
tree[2 * x + 2].lazy += tree[x].lazy;
tree[x].lazy = 0;
}
void upd(int l, int r, long long value, int x, int lx, int rx) {
propagate(x, lx, rx);
if(lx >= r || rx <= l) {
return;
}
if(lx >= l && rx <= r) {
tree[x] = {tree[x].value + (rx - lx) * value, value};
propagate(x, lx, rx);
return;
}
int mid = (lx + rx) / 2;
upd(l, r, value, 2 * x + 1, lx, mid);
upd(l, r, value, 2 * x + 2, mid, rx);
tree[x].value = tree[2 * x + 1].value + tree[2 * x + 2].value;
}
void upd(int l, int r, long long value) {
upd(l, r, value, 0, 0, size);
}
long long qry(int l, int r, int x, int lx, int rx) {
propagate(x, lx, rx);
if(lx >= r || rx <= l) {
return 0;
}
if(lx >= l && rx <= r) {
return tree[x].value;
}
int mid = (lx + rx) / 2;
long long s1 = qry(l, r, 2 * x + 1, lx, mid);
long long s2 = qry(l, r, 2 * x + 2, mid, rx);
return s1 + s2;
}
long long qry(int l, int r) {
return qry(l, r, 0, 0, size);
}
};
segTreeSum seg_sum;
void solve_() {
cin >> n >> m >> q;
int oki = 1;
for(int i = 0; i < q; i++) {
int type; cin >> type;
if(type == 1) {
long long l, r, c, k;
cin >> l >> r >> c >> k;
queries.push_back({type, l, r, k, c});
} else if(type == 2) {
long long l, r, k; cin >> l >> r >> k;
queries.push_back({type, l, r, k, -1});
oki = 0;
} else {
long long l, r; cin >> l >> r;
queries.push_back({type, l, r, -1, -1});
}
}
// if(oki) {
seg.init(q + 1);
seg_sum.init(q + 1);
vector<long long> answ(q + 1), out(q + 1);
for(int i = 0; i < q; i++) {
int type = queries[i].type;
if(type == 1) {
long long l = queries[i].l;
long long r = queries[i].r;
long long c = queries[i].c;
long long k = queries[i].k;
to_add[l].push_back({i, {k, c}});
to_del[r + 1].push_back({i, {k, c}});
} else if(type == 3) {
long long a = queries[i].l;
long long b = queries[i].r;
qq[a].push_back({i, {b, -1}});
out[i] = 1;
} else {
long long l = queries[i].l;
long long r = queries[i].r;
long long k = queries[i].k;
to_add2[l].push_back({i, {k, -1}});
to_del2[r + 1].push_back({i, {k, -1}});
}
}
for(int i = 1; i <= n; i++) {
for(auto j: to_add[i]) {
seg.upd(j.first, j.first + 1, j.second.first, j.second.second);
}
for(auto j: to_del[i]) {
seg.upd(j.first, j.first + 1, -1, -1);
}
for(auto j: to_add2[i]) {
seg_sum.upd(j.first, j.first + 1, j.second.first);
}
for(auto j: to_del2[i]) {
seg_sum.upd(j.first, j.first + 1, -j.second.first);
}
for(auto j: qq[i]) {
long long pre = seg_sum.qry(0, j.first + 1);
dbg(j.second.first + pre)
auto u = seg.qry(j.second.first + pre);
dbg(u)
if(u.first == 0) {
answ[j.first] = u.first;
} else if(u.second > j.first) {
answ[j.first] = 0;
} else {
answ[j.first] = u.first;
}
}
}
for(int i = 0; i < q; i++) {
if(out[i]) {
cout << answ[i] << '\n';
}
}
// } else {
// long long it = 0, ok = 1;
// set<int> not_empty;
// vector<bool> have(n + 1);
// for(int t = 0; t < q; t++) {
// int type = queries[t].type;
// if(type == 1) {
// long long l, r, c, k;
// l = queries[t].l;
// r = queries[t].r;
// c = queries[t].c;
// k = queries[t].k;
// for(int i = l; i <= r; i++) {
// cnt[i] += k;
// st[i].push_back({it, {c, k}});
// if(!have[i]) {
// have[i] = true;
// not_empty.insert(i);
// }
// }
// if(k != 1) ok = 0;
// } else if(type == 2) {
// long long l, r, k;
// l = queries[t].l;
// r = queries[t].r;
// k = queries[t].k;
// if(k != 1) ok = 0;
// auto it = not_empty.lower_bound(l);
// vector<int> to_del;
// while(it != not_empty.end() && *it <= r) {
// int i = *it;
// if(ok) {
// if(!st[i].empty()) {
// st[i].pop_front();
// }
// } else {
// long long curr = k;
// while(!st[i].empty()) {
// if(curr >= st[i].front().second.second) {
// curr -= st[i].front().second.second;
// st[i].pop_front();
// } else {
// st[i].front().second.second -= curr;
// break;
// }
// }
// }
// cnt[i] -= k;
// cnt[i] = max(cnt[i], 0ll);
// if(cnt[i] == 0) {
// to_del.push_back(i);
// }
// it = next(it);
// }
// for(auto i: to_del) {
// have[i] = false;
// not_empty.erase(i);
// }
// } else {
// long long a, b;
// // cin >> a >> b;
// a = queries[t].l;
// b = queries[t].r;
// if(cnt[a] < b) {
// cout << 0 << '\n';
// } else {
// if(ok) {
// cout << st[a][b - 1].second.first << '\n';
// } else {
// for(int i = 0; i < sz(st[a]); i++) {
// if(b > st[a][i].second.second) {
// b -= st[a][i].second.second;
// } else {
// cout << st[a][i].second.first << '\n';
// break;
// }
// }
// }
// }
// }
// it++;
// }
// }
}
int main() {
setIO();
auto solve = [&](int test_case)-> void {
while(test_case--) {
solve_();
}
};
int test_cases = 1;
// cin >> test_cases;
solve(test_cases);
return 0;
}
Compilation message
foodcourt.cpp: In function 'void solve_()':
foodcourt.cpp:273:7: warning: variable 'oki' set but not used [-Wunused-but-set-variable]
273 | int oki = 1;
| ^~~
foodcourt.cpp: In function 'void setIO(std::string)':
foodcourt.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen((str + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | freopen((str + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
194380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
194380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
517 ms |
208252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1112 ms |
244984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
194380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
613 ms |
208268 KB |
Output is correct |
| 2 |
Correct |
641 ms |
209072 KB |
Output is correct |
| 3 |
Correct |
641 ms |
209408 KB |
Output is correct |
| 4 |
Correct |
495 ms |
206296 KB |
Output is correct |
| 5 |
Correct |
595 ms |
207808 KB |
Output is correct |
| 6 |
Correct |
633 ms |
209396 KB |
Output is correct |
| 7 |
Correct |
606 ms |
208096 KB |
Output is correct |
| 8 |
Correct |
561 ms |
208112 KB |
Output is correct |
| 9 |
Correct |
607 ms |
209172 KB |
Output is correct |
| 10 |
Correct |
478 ms |
206372 KB |
Output is correct |
| 11 |
Correct |
625 ms |
209236 KB |
Output is correct |
| 12 |
Correct |
664 ms |
209268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
194380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
194380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
