| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1177087 | sleepntsheep | 푸드 코트 (JOI21_foodcourt) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <stdio.h>
using namespace std;
template<typename T>
using ve=std::vector<T>;
using pii=std::pair<int,int>;
int n, m, q;
struct Q{
int t,a,b,c,d;
long long k;
};
struct S{
struct node{
long long sum,pre,suf,ans;
node(){ sum=pre=suf=ans=0; }
friend node operator+(const node&a,const node&b){
node c;
c.sum=a.sum+b.sum;
c.pre=std::max({a.pre,a.sum+b.pre});
c.suf=std::max({b.suf,b.sum+a.suf});
c.ans=std::max({a.ans,b.ans,a.suf+b.pre});
return c;
}
};
ve<node>t;
S(){}
~S(){}
int n;
void init(int n0){
n=n0;t.assign(n*2,node());
}
void pul(int p){
t[p]=t[p*2]+t[p*2+1];
}
void upd(int p,long long k){
p+=n;
t[p].sum+=k;
t[p].pre+=k;
t[p].suf+=k;
t[p].ans+=k;
t[p].pre=std::max(t[p].pre,0ll); t[p].suf=std::max(t[p].suf,0ll); t[p].ans=std::max(t[p].ans,0ll);
for(;p/=2;)pul(p);
}
node qry(int l,int r){
node zl,zr;
for(l+=n,r+=n+1;l<r;l/=2,r/=2){
if(l&1)zl=zl+t[l++];
if(r&1)zr=t[--r]+zr;
}
return zl+zr;
}
} st;
struct F{
ve<long long>t;
int n;
F(){}
~F(){}
void init(int n0){
t.assign(n=n0,0);
}
void add(int p,long long k){
for(;p<n;p|=p+1)t[p]+=k;
}
long long sum(int p){
long long z=0;
for(;p;p&=p-1)z+=t[p-1];
return z;
}
} fw;
int main() {
scanf("%d%d%d", &n, &m, &q);
ve<Q>qq(q);
ve<ve<int>>e(555555);
ve<long long>cur(q),tot(q);
st.ini(555555);
fw.init(555555);
for (int i = 0; i < q; ++i) {
scanf("%d", &qq[i].t);
if (qq[i].t == 1) {
scanf("%d%d%d%d", &qq[i].a, &qq[i].b, &qq[i].c, &qq[i].d);
ev[qq[i].a].push_back(i);
ev[qq[i].b+1].push_back(i);
fw.add(qq[i].a,qq[i].d);
fw.add(qq[i].b+1,-qq[i].d);
} else if (qq[i].t == 2) {
scanf("%d%d%d", &qq[i].a, &qq[i].b, &qq[i].c);
ev[qq[i].a].push_back(i);
ev[qq[i].b+1].push_back(i);
} else {
scanf("%d%lld", &qq[i].a, &qq[i].k);
ev[qq[i].a].push_back(i);
tot[i]=fw.sum(qq[i].a+1);
}
}
for(int i=1;i<=n;++i){
for(auto sec:ev[i]){
auto[typ,a,b,c,d,k]=qq[sec];
if(typ==1){
st.upd(sec,a==i?d:-d);
}else if(typ==2){
st.upd(sec,b+1==i?d:-d);
}else{
auto x=st.qry(0,sec);
cur[sec]=x.ans;
}
}
}
for(int i=0;i<q;++i){
auto[typ,a,b,c,d,k]=qq[i];
if(typ==3){
if(cur[i]>=k)puts("1");
else puts("0");
}
}
return 0;
}