#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int s,e;
int lazymin,lazych;
int v;
node *l,*r;
node (int _s, int _e){
s = _s; e = _e;
lazymin = 0; lazych = 0;
v = 0;
if (s!=e){
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
}
}
void proc(){
if (lazymin==0 && lazych==0) return;
if (s!=e){
l->lazymin = min(l->lazymin,l->lazych+lazymin);
l->lazych += lazych;
r->lazymin = min(r->lazymin,r->lazych+lazymin);
r->lazych += lazych;
}
if (s==e){
v += lazymin;
v = max(v,0LL);
v -= lazymin;
v += lazych;
}
lazymin = 0;
lazych = 0;
}
void inc(int a, int b, int val){
proc();
if (a<=s && e<=b){
lazych += val;
proc();
return;
}
else if (b<=(s+e)/2){
l->inc(a,b,val);
}
else if (a>(s+e)/2){
r->inc(a,b,val);
}
else{
l->inc(a,b,val);
r->inc(a,b,val);
}
l->proc();
r->proc();
}
void dec(int a, int b, int val){
proc();
if (a<=s && e<=b){
lazych -= val;
lazymin = min(lazymin,lazych);
proc();
return;
}
else if (b<=(s+e)/2){
l->dec(a,b,val);
}
else if (a>(s+e)/2){
r->dec(a,b,val);
}
else{
l->dec(a,b,val);
r->dec(a,b,val);
}
l->proc(); r->proc();
}
int qu(int pos){
proc();
if (s==e) return v;
if (pos>(s+e)/2)return r->qu(pos);
else return l->qu(pos);
}
}*root;
struct q_dat{
int l,r;
int t,k;
q_dat(){
l = 0; r = 0; t = 0; k = 0;
}
q_dat(int _l, int _r, int _t, int _k){
l = _l; r = _r; t = _t; k = _k;
}
};
//vector<q_dat> query1;
int groupnum[250005];
//vector<q_dat> query2;
vector<pair<pair<int,int>,int> > query3;
int fw[250005];
void upd(int pos, int val){
while (pos<250005){
fw[pos] += val;
pos+=pos&-pos;
}
}
int qu(int pos){
int ans = 0;
while (pos>0){
ans += fw[pos];
pos -= pos&-pos;
}
return ans;
}
int numt[250005];
int ans[250005];
vector<pair<pair<int,int>,int> > bsvals[250005];
vector<pair<pair<int,int>,int> > bsvals2[250005];
struct node2{
int s, e;
int lazyval;
node2 *l,*r;
node2 (int _s, int _e){
s = _s; e = _e;
lazyval = -1;
if (s!=e){
l = new node2(s,(s+e)/2);
r = new node2((s+e)/2+1,e);
}
}
void proc(){
if (lazyval==-1) return;
if (s!=e){
l->lazyval = lazyval;
r->lazyval = lazyval;
lazyval = -1;
}
}
int qu(int pos){
proc();
if (s==e) return lazyval;
if (pos<=(s+e)/2) return l->qu(pos);
return r->qu(pos);
}
void upd(int a, int b, int val){
proc();
if (a<=s && e<=b) {
lazyval = val;
proc();
return;
}
if (b<=(s+e)/2){
l->upd(a,b,val);
}
else if (a>(s+e)/2){
r->upd(a,b,val);
}
else{
l->upd(a,b,val);
r->upd(a,b,val);
}
}
}*root2;
int incl[250005];
int incr[250005];
int incamt[250005];
int finans[250005];
main(){
int n,m,q;
scanf("%lld%lld%lld",&n,&m,&q);
root = new node(1,n);
for (int x = 0; x<q; x++){
int a;
scanf("%lld",&a);
if (a==1){
int b,c,d,e;
scanf("%lld%lld%lld%lld",&b,&c,&d,&e);
groupnum[x] = d;
// query1.push_back(q_dat(b,c,x,e));
root->inc(b,c,e);
upd(b,e);
upd(c+1,-e);
incl[x] = b;
incr[x] = c;
incamt[x] = e;
}
else if (a==2){
int b,c,d;
scanf("%lld%lld%lld",&b,&c,&d);
// query2.push_back(q_dat(b,c,x,d));
root->dec(b,c,d);
}
else if (a==3){
int b,c;
scanf("%lld%lld",&b,&c);
query3.push_back({{b,c},x});
int num = root->qu(b);
numt[x] = qu(b)-num+c;
incl[x] = b;
if (num<c){
ans[x] = -1;
}
//printf("%lld has %lld\n",b,numpopped[x]);
}
}
for (auto x : query3){
if (ans[x.second]==-1) continue;
int a = -1;
int b = q-1;
int mid = (a+b)/2;
bsvals[mid].push_back({{a,b},x.second});
}
bool found = true;
while (found){
found = false;
for (int k = 0; k<250005; k++){
fw[k] = 0;
}
for (int t = 0; t<q; t++){
if (incamt[t]!=0){
upd(incl[t],incamt[t]);
upd(incr[t]+1,-incamt[t]);
}
for (auto x : bsvals[t]){
if (x.first.first+1==x.first.second) {
ans[x.second] = x.first.second;
assert(ans[x.second]<x.second);
continue;
}
if (qu(incl[x.second])>=numt[x.second]){
bsvals2[(x.first.first+t)/2].push_back({{x.first.first,t},x.second});
}
else{
bsvals2[(x.first.second+t)/2].push_back({{t,x.first.second},x.second});
}
found = true;
}
bsvals[t].clear();
}
swap(bsvals2,bsvals);
}
root2 = new node2(1,n);
vector<pair<pair<int,int>,int> > stuff;
for (auto x : query3){
if (ans[x.second]==-1) {
continue;
}
stuff.push_back({{ans[x.second],incl[x.second]},x.second});
}
sort(stuff.begin(),stuff.end());
int curt = 0;
for (auto x : stuff){
while (curt<=x.first.first){
if (incamt[curt]!=0){
root2->upd(incl[curt],incr[curt],curt);
//printf("set %lld to %lld with %lld\n",incl[curt],incr[curt],curt);
}
curt++;
}
finans[x.second] = root2->qu(x.first.second);
//printf("query %lld = %lld\n",x.first.second,finans[x.second]);
}
for (auto x : query3){
// printf("ans = %lld\n",ans[x.second]);
if (finans[x.second]==0){
printf("0\n");
}
else{
assert(finans[x.second]!=-1);
printf("%lld\n",groupnum[finans[x.second]]);
}
}
}
Compilation message
foodcourt.cpp:173:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
173 | main(){
| ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | scanf("%lld%lld%lld",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
179 | scanf("%lld",&a);
| ~~~~~^~~~~~~~~~~
foodcourt.cpp:182:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
182 | scanf("%lld%lld%lld%lld",&b,&c,&d,&e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:194:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | scanf("%lld%lld%lld",&b,&c,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:200:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
200 | scanf("%lld%lld",&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
31920 KB |
Output is correct |
| 2 |
Correct |
172 ms |
31756 KB |
Output is correct |
| 3 |
Correct |
161 ms |
31908 KB |
Output is correct |
| 4 |
Correct |
164 ms |
31908 KB |
Output is correct |
| 5 |
Correct |
201 ms |
31760 KB |
Output is correct |
| 6 |
Correct |
206 ms |
31764 KB |
Output is correct |
| 7 |
Correct |
109 ms |
21444 KB |
Output is correct |
| 8 |
Correct |
109 ms |
21896 KB |
Output is correct |
| 9 |
Correct |
162 ms |
31668 KB |
Output is correct |
| 10 |
Correct |
173 ms |
31764 KB |
Output is correct |
| 11 |
Correct |
175 ms |
31572 KB |
Output is correct |
| 12 |
Correct |
168 ms |
31732 KB |
Output is correct |
| 13 |
Correct |
150 ms |
29968 KB |
Output is correct |
| 14 |
Correct |
202 ms |
35388 KB |
Output is correct |
| 15 |
Correct |
179 ms |
27636 KB |
Output is correct |
| 16 |
Correct |
221 ms |
32184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
978 ms |
108912 KB |
Output is correct |
| 2 |
Correct |
748 ms |
92260 KB |
Output is correct |
| 3 |
Execution timed out |
1022 ms |
118040 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
42436 KB |
Output is correct |
| 2 |
Correct |
234 ms |
42092 KB |
Output is correct |
| 3 |
Incorrect |
249 ms |
44676 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
14540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
