#include <bits/stdc++.h>
#define int long long
#define INF (1LL << 60)
using namespace std;
struct node{
node(){ };
node(int k, int c) { pmax = sum = k; colour = c; }
int pmax = -INF, sum = 0, colour = 0;
friend node operator+ (const node& L, const node& R){
node res;
res.pmax = max(L.pmax, L.sum + R.pmax);
res.sum = L.sum + R.sum;
return res;
}
};
const int N_MAX = 2.5e5 + 11;
node t[N_MAX << 2];
void add(int idx, int k, int c = 0, int v = 0, int tl = 0, int tr = N_MAX - 1){
// if(v == 0) cout << "ADD " << idx << ' ' << k << ' ' << c << endl;
if(tl == tr){
t[v] = node(k, c);
return;
}
int tm = (tl + tr) / 2;
if(idx <= tm){
add(idx, k, c, v * 2 + 1, tl, tm);
}else{
add(idx, k, c, v * 2 + 2, tm + 1, tr);
}
t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}
int qry(int idx, int k, int v = 0, int tl = 0, int tr = N_MAX - 1){
// if(v == 0) cout << "QRY " << idx << ' ' << k << endl;
if(tl == tr) return t[v].pmax >= k ? t[v].colour : 0;
int tm = (tl + tr) / 2;
if(idx <= tm){
return qry(idx, k, v * 2 + 1, tl, tm);
}else{
int q1 = qry(idx, k, v * 2 + 1, tl, tm);
int q2 = qry(idx, k - t[v * 2 + 1].sum, v * 2 + 2, tm + 1, tr);
// cout << q1 << ' ' << q2 << endl;
return q2 ? q2 : q1;
}
}
int sum(int idx, int v = 0, int tl = 0, int tr = N_MAX - 1){
if(tl == tr) return t[v].sum;
int tm = (tl + tr) / 2;
if(idx <= tm){
return sum(idx, v * 2 + 1, tl, tm);
}else{
int q1 = sum(idx, v * 2 + 1, tl, tm);
int q2 = sum(idx, v * 2 + 2, tm + 1, tr);
return q1 + q2;
}
}
struct query{
int p, i, t, c, k;
};
vector<query> Q;
int32_t main(){
cin.tie(0);
cout.tie(0)->sync_with_stdio(false);
int n, m, q; cin >> n >> m >> q;
for(int i = 0; i < q; i++){
int l, r, a, c, k;
int t; cin >> t;
switch(t){
case 1: t = 1; cin >> l >> r >> c >> k; Q.push_back({l, i, 1, c, k}); Q.push_back({r + 1, i, 1, 0, 0}); break;
case 2: t = 2; cin >> l >> r >> k; Q.push_back({l, i, 1, 0, -k}); Q.push_back({r + 1, i, 1, 0, 0}); break;
case 3: t = 3; cin >> a >> k; Q.push_back({a, i, 2, 0, k}); break;
}
}
sort(Q.begin(), Q.end(), [](query a, query b){
return a.p < b.p || a.p == b.p && a.i < b.i;
});
map<int, int> ans;
for(auto& q : Q){
if(q.t == 1) add(q.i, q.k, q.c);
else {
ans[q.i] = sum(q.i) >= q.k ? 1 : 0;
}
}
for(auto [i, j] : ans){
cout << j << endl;
}
}
Compilation message
foodcourt.cpp: In lambda function:
foodcourt.cpp:83:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
83 | return a.p < b.p || a.p == b.p && a.i < b.i;
| ~~~~~~~~~~~^~~~~~~~~~~~
foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:92:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
92 | for(auto [i, j] : ans){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1041 ms |
29840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1069 ms |
48416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1055 ms |
30268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
