Submission #789484

#	Time	Username	Problem	Language	Result	Execution time	Memory
789484		winter0101	Food Court (JOI21_foodcourt)	C++14	100 / 100	502 ms	68988 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+5e4+9;
struct node{
long long mx,lazy;
bool mxup;
node(){
mx=0;
mxup=0;
lazy=0;
}
}st[maxn*4];
void push(int id){
if (st[id].mxup){
if (!st[id*2].mxup){
    st[id*2].mxup=1;
    st[id*2].mx=st[id].mx;
    st[id*2].lazy+=st[id].lazy;
}
else {
    st[id*2].mx=max(st[id*2].mx+st[id].lazy,st[id].mx);
    st[id*2].lazy+=st[id].lazy;
}
if (!st[id*2+1].mxup){
    st[id*2+1].mxup=1;
    st[id*2+1].mx=st[id].mx;
    st[id*2+1].lazy+=st[id].lazy;
}
else {
    st[id*2+1].mx=max(st[id*2+1].mx+st[id].lazy,st[id].mx);
    st[id*2+1].lazy+=st[id].lazy;
}
st[id].mx=0;
st[id].lazy=0;
st[id].mxup=0;
}
else {
    if (!st[id*2].mxup){
    st[id*2].lazy+=st[id].lazy;
    }
    else {
    st[id*2].mx+=st[id].lazy;
    st[id*2].lazy+=st[id].lazy;
    }
    if (!st[id*2+1].mxup){
    st[id*2+1].lazy+=st[id].lazy;
    }
    else {
    st[id*2+1].mx+=st[id].lazy;
    st[id*2+1].lazy+=st[id].lazy;
    }
    st[id].lazy=0;
}
}
void update(int id,int l,int r,int u,int v,long long val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    if (!st[id].mxup){
        st[id].lazy+=val;
    }
    else {
        st[id].mx+=val;
        st[id].lazy+=val;
    }
    return;
}
int mid=(l+r)/2;
push(id);
update(id*2,l,mid,u,v,val);
update(id*2+1,mid+1,r,u,v,val);
}
void update2(int id,int l,int r,int u,int v,long long val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    if (!st[id].mxup){
        st[id].mxup=1;
        st[id].mx=val;
    }
    else st[id].mx=max(st[id].mx,val);
    return;
}
int mid=(l+r)/2;
push(id);
update2(id*2,l,mid,u,v,val);
update2(id*2+1,mid+1,r,u,v,val);
}
long long get(int id,int l,int r,int u){
while (true){
if (l==r){
    return st[id].mx;
}
push(id);
int mid=(l+r)/2;
if (mid>=u){
    r=mid;
    id=id*2;
}
else {
    l=mid+1;
    id=id*2+1;
}
}
}
long long bit[maxn];
long long shop[maxn];
long long tk[maxn];
int n,m,q;
void add(int pos,long long val){
for(;pos<=q;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
long long get(int pos){
long long sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
long long get(int l,int r){
return get(r)-get(l-1);
}
struct range{
int l,r,c;
long long k;
}b[maxn];
vector<int>ad[maxn],dl[maxn];
vector<int>qr[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>m>>q;
    for1(i,1,n)update2(1,1,n,i,i,0);
    for1(i,1,q){
    int t;
    cin>>t;
    shop[i]=-1;
    if (t==3){
        int x;
        long long y;
        cin>>x>>y;
        qr[x].pb(i);
        tk[i]=y;
        shop[i]=get(1,1,n,x);
    }
    if (t==2){
        int l,r;
        long long k;
        cin>>l>>r>>k;
        update(1,1,n,l,r,-k);
        update2(1,1,n,l,r,0);
    }
    if (t==1){
        int l,r,c;
        long long k;
        cin>>l>>r>>c>>k;
        ad[l].pb(i);
        dl[r].pb(i);
        b[i]={l,r,c,k};
        update(1,1,n,l,r,k);
    }
    }
    for1(i,1,n){
    for (auto v:ad[i]){
        add(v,b[v].k);
    }
    for (auto v:qr[i]){
        //long long haveicecream=tk[v];
        if (shop[v]<tk[v]){
            shop[v]=0;
            continue;
        }
        long long diff=shop[v]-tk[v]+1;
        int l=1,r=v-1,asn=v;
        while (l<=r){
            int mid=(l+r)/2;
            if (get(mid,v)>=diff){
                asn=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        shop[v]=b[asn].c;
    }
    for (auto v:dl[i]){
        add(v,-b[v].k);
    }
    }
    for1(i,1,q){
    if (tk[i]){
        cout<<shop[i]<<'\n';
    }
    }



}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11