#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
class SegmentTree{
struct node_t{
long long a,b;///LEAVE a, JOIN b
node_t operator + (const node_t &other)const{
node_t ans;
ans = *this;
ans.b -= other.a;
if(ans.b < 0){
ans.a -= ans.b;
ans.b = 0;
}
ans.b += other.b;
return ans;
}
node_t(){
a = b = 0;
}
node_t(long long a,long long b){
this->a = a;
this->b = b;
}
};
int n;
vector<node_t> aint;
void propagate(int nod,int st,int dr){
if(st == dr){
return ;
}
aint[nod * 2] = aint[nod * 2] + aint[nod];
aint[nod * 2 + 1] = aint[nod * 2 + 1] + aint[nod];
aint[nod] = node_t();
}
void update(int nod,int st,int dr,int l,int r,node_t val){
propagate(nod,st,dr);
if(dr < l || st > r){
return ;
}
if(l <= st && dr <= r){
aint[nod] = aint[nod] + val;
return ;
}
int mid = (st + dr) / 2;
update(nod * 2,st,mid,l,r,val);
update(nod * 2 + 1,mid + 1,dr,l,r,val);
}
node_t access(int nod,int st,int dr,int pos){
propagate(nod,st,dr);
if(dr < pos || st > pos){
return node_t();
}
if(st == dr){
return aint[nod];
}
int mid = (st + dr) / 2;
return access(nod * 2,st,mid,pos) + access(nod * 2 + 1,mid + 1,dr,pos);
}
public:
SegmentTree(int n){
this->n = n;
this->aint = vector<node_t>(4 * n + 5);
}
void add(int l,int r,long long value){
update(1,1,n,l,r,{0,value});
}
void remove(int l,int r,long long value){
update(1,1,n,l,r,{value,0});
}
long long access(int pos){
return access(1,1,n,pos).b;
}
};
class FenwickTree{
int n;
vector<long long> aib;
void update(int pos,long long value){
for(;pos <= n;pos += (-pos) & pos){
aib[pos] += value;
}
}
long long query(int pos){
long long ans = 0;
for(;pos;pos -= (-pos) & pos){
ans += aib[pos];
}
return ans;
}
public:
FenwickTree(int n){
this->n = n;
this->aib = vector<long long>(n + 1);
}
void add(int l,int r,long long value){
update(l,value);
update(r + 1,-value);
}
long long access(int pos){
return query(pos);
}
};
class SegmentTree2{///cause why not
int n;
vector<pair<long long,int> > aint;
vector<long long> lazy;
void propagate(int nod,int st,int dr){
if(lazy[nod] == 0 || st == dr){
return ;
}
lazy[nod * 2] += lazy[nod];
lazy[nod * 2 + 1] += lazy[nod];
aint[nod * 2].first -= lazy[nod];
aint[nod * 2 + 1].first -= lazy[nod];
lazy[nod] = 0;
}
void build(int nod,int st,int dr){
if(st == dr){
aint[nod] = {0,st};
return ;
}
int mid = (st + dr) / 2;
build(nod * 2,st,mid);
build(nod * 2 + 1,mid + 1,dr);
aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
}
void update_range(int nod,int st,int dr,int l,int r,long long value){
propagate(nod,st,dr);
if(r < st || l > dr){
return ;
}
if(l <= st && dr <= r){
aint[nod].first -= value;
lazy[nod] += value;
return ;
}
int mid = (st + dr) / 2;
update_range(nod * 2,st,mid,l,r,value);
update_range(nod * 2 + 1,mid + 1,dr,l,r,value);
aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
}
void update_set(int nod,int st,int dr,int pos,long long value){
propagate(nod,st,dr);
if(dr < pos || st > pos){
return ;
}
if(st == dr){
aint[nod].first = value;
return ;
}
int mid = (st + dr) / 2;
update_set(nod * 2,st,mid,pos,value);
update_set(nod * 2 + 1,mid + 1,dr,pos,value);
aint[nod] = min(aint[nod * 2],aint[nod * 2 + 1]);
}
public:
SegmentTree2(int n){
this->n = n;
aint = vector<pair<long long,int> >(4 * n + 5);
lazy = vector<long long>(4 * n + 5);
build(1,1,n);
}
void update_range(int l,int r,long long value){
update_range(1,1,n,l,r,value);
}
void update_set(int pos,long long value){
update_set(1,1,n,pos,value);
}
pair<long long,int> query(){
return aint[1];
}
};
const int NMAX = 250000;
const int MMAX = 250000;
const int QMAX = 250000;
int n,m,q;
struct query_t{
int l,r,c;
long long k;
};
deque<pair<long long,int> > queries[NMAX + 5];
int answer[QMAX + 5];
int main(){
scanf("%d %d %d",&n,&m,&q);
vector<query_t> query_list;
SegmentTree aint(n);
FenwickTree aib(n);
for(int i = 1;i <= q;i++){
int t;
scanf("%d",&t);
if(t == 1){
int l,r,c;
long long k;
scanf("%d %d %d %lld",&l,&r,&c,&k);
aint.add(l,r,k);
aib.add(l,r,k);
query_list.push_back({l,r,c,k});
}else if(t == 2){
int l,r;
long long k;
scanf("%d %d %lld",&l,&r,&k);
aint.remove(l,r,k);
}else{
int a;
long long b;
scanf("%d %lld",&a,&b);
long long total = aib.access(a);
long long cnt = aint.access(a);
if(cnt >= b){
queries[a].push_back({total - cnt + b,i});
}else{
answer[i] = -1;
}
}
}
SegmentTree2 aint2(n);
for(int i = 1;i <= n;i++){
sort(queries[i].begin(),queries[i].end());
if(queries[i].empty()){
aint2.update_set(i,1e18);
}else{
aint2.update_set(i,queries[i].front().first);
}
}
for(auto it:query_list){
aint2.update_range(it.l,it.r,it.k);
while(aint2.query().first <= 0){
int pos = aint2.query().second;
answer[queries[pos].front().second] = it.c;
queries[pos].pop_front();
if(queries[pos].empty()){
aint2.update_set(pos,1e18);
}else{
aint2.update_range(pos,pos,-queries[pos].front().first);///Ugly? yes. does it work? i hope so
}
}
}
for(int i = 1;i <= q;i++){
if(answer[i] != 0){
printf("%d\n",(answer[i] == -1 ? 0:answer[i]));
}
}
return 0;
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:246:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
246 | scanf("%d %d %d",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:255:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
255 | scanf("%d",&t);
| ~~~~~^~~~~~~~~
foodcourt.cpp:260:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
260 | scanf("%d %d %d %lld",&l,&r,&c,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:267:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
267 | scanf("%d %d %lld",&l,&r,&k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:272:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
272 | scanf("%d %lld",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
168844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
168844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
471 ms |
180152 KB |
Output is correct |
| 2 |
Correct |
305 ms |
180424 KB |
Output is correct |
| 3 |
Incorrect |
236 ms |
180176 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
849 ms |
208440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
168844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
261 ms |
180084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
168844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
168844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
