#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int,ll> ii;
struct up{ int l,r,c;ll k; };
vector<up> ups;
struct qry{ int l,i;ll k; };
struct thing{
int s,e;
vector<qry> v;
};
queue<thing> qe;
int n,m,q,t,l,r,c,ans[65005];
ll k,ft[65005],INF=1e15;
void upd(int x,int y,ll v){
while(x<=n)ft[x]+=v,x+=x&-x;
++y;
while(y<=n)ft[y]-=v,y+=y&-y;
}
ll query(int x){
ll res=0;
while(x)res+=ft[x],x-=x&-x;
return res;
}
int main(){
sf("%d%d%d",&n,&m,&q);
thing th={0,0};
for(int i=0;i<q;++i){
sf("%d",&t);
if(t==1){
sf("%d%d%d%lld",&l,&r,&c,&k);
ups.pb({l,r,c,k});
}
if(t==3){
sf("%d%lld",&l,&k);
th.v.pb({l,i,k});
}
}
memset(ans,-1,sizeof ans);
th.e=ups.size();
qe.push(th);
int pv=-1;
while(!qe.empty()){
thing th=qe.front();qe.pop();
if(th.s==th.e){
for(auto qq:th.v){
if(th.s==ups.size())ans[qq.i]=0;
else ans[qq.i]=ups[th.s].c;
}
continue;
}
int m=(th.s+th.e)/2;
thing nl={th.s,m},nr={m+1,th.e};
if(m<pv){
memset(ft,0,sizeof ft);
pv=-1;
}
while(pv<m){
++pv;
upd(ups[pv].l,ups[pv].r,ups[pv].k);
}
for(auto qq:th.v){
if(qq.k<=query(qq.l))nl.v.pb(qq);
else nr.v.pb(qq);
}
if(nl.v.size()>0)qe.push(nl);
if(nr.v.size()>0)qe.push(nr);
}
for(int i=0;i<q;++i)if(ans[i]!=-1)pf("%d\n",ans[i]);
}
/*
3 5 6
1 2 3 5 2
1 1 2 2 4
3 2 3
3 1 2
1 2 3 4 2
3 3 2
3 4 7
1 1 2 1 1
1 1 3 4 1
2 2 3 1
2 1 3 1
1 1 2 2 1
3 1 1
3 3 2
*/
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<up>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if(th.s==ups.size())ans[qq.i]=0;
| ~~~~^~~~~~~~~~~~
foodcourt.cpp:36:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | sf("%d%d%d",&n,&m,&q);
| ^
foodcourt.cpp:39:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | sf("%d",&t);
| ^
foodcourt.cpp:41:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | sf("%d%d%d%lld",&l,&r,&c,&k);
| ^
foodcourt.cpp:45:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | sf("%d%lld",&l,&k);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
2244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
6328 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
3736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
