Submission #1208806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208806		guagua0407	Food Court (JOI21_foodcourt)	C++20	100 / 100	402 ms	74780 KiB

foodcourt

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=250005;

struct st1{
    struct node{
        ll sum,cur,add,del,add2;
    };
    vector<node> st;
    st1(){
        st.resize(mxn*4);
    }
    void push(int v){
        if(st[v].del!=0){
            //cout<<v<<'\n';
            int val=st[v].del;
            st[v*2].cur=max(0ll,st[v*2].cur-val);
            if(st[v*2].add!=0){
                if(st[v*2].add>=val) st[v*2].add-=val;
                else{
                    st[v*2].del+=val-st[v*2].add;
                    st[v*2].add=0;
                }
            }
            else{
                st[v*2].del+=val;
            }
            st[v*2+1].cur=max(0ll,st[v*2+1].cur-val);
            if(st[v*2+1].add!=0){
                if(st[v*2+1].add>=val) st[v*2+1].add-=val;
                else{
                    st[v*2+1].del+=val-st[v*2+1].add;
                    st[v*2+1].add=0;
                }
            }
            else{
                st[v*2+1].del+=val;
            }
            st[v].del=0;
        }
        if(st[v].add!=0){
            int val=st[v].add;
            //st[v*2].sum+=val;
            st[v*2].cur+=val;
            st[v*2].add+=val;
            //st[v*2+1].sum+=val;
            st[v*2+1].cur+=val;
            st[v*2+1].add+=val;
            st[v].add=0;
        }
        if(st[v].add2!=0){
            int val=st[v].add2;
            st[v*2].sum+=val;
            st[v*2].add2+=val;
            st[v*2+1].sum+=val;
            st[v*2+1].add2+=val;
            st[v].add2=0;
        }
    }
    void add(int tl,int tr,int val,int l=0,int r=mxn-1,int v=1){
        if(r<tl or tr<l){
            return;
        }
        if(tl<=l and r<=tr){
            st[v].sum+=val;
            st[v].cur+=val;
            st[v].add+=val;
            st[v].add2+=val;
            return;
        }
        push(v);
        int mid=(l+r)/2;
        add(tl,min(mid,tr),val,l,mid,v*2);
        add(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
    }
    void del(int tl,int tr,int val,int l=0,int r=mxn-1,int v=1){
        if(r<tl or tr<l){
            return;
        }
        if(tl<=l and r<=tr){
            st[v].cur=max(0ll,st[v].cur-val);
            if(st[v].add!=0){
                if(st[v].add>=val) st[v].add-=val;
                else{
                    st[v].del+=val-st[v].add;
                    st[v].add=0;
                }
            }
            else{
                st[v].del+=val;
            }
            return;
        }
        push(v);
        int mid=(l+r)/2;
        del(tl,min(mid,tr),val,l,mid,v*2);
        del(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
    }
    int query(int pos,int l=0,int r=mxn-1,int v=1){
        if(l==r){
            //cout<<st[v].cur<<' '<<st[v].sum<<'\n';
            return st[v].sum-st[v].cur;
        }
        push(v);
        int mid=(l+r)/2;
        if(pos<=mid) return query(pos,l,mid,v*2);
        else return query(pos,mid+1,r,v*2+1);
    }
};

struct st2{
    struct node{
        ll mx,add;
    };
    vector<node> st;
    st2(){
        st.resize(mxn*4);
    }
    void push(int v){
        if(st[v].add!=0){
            int val=st[v].add;
            st[v*2].mx+=val;
            st[v*2].add+=val;
            st[v*2+1].mx+=val;
            st[v*2+1].add+=val;
            st[v].add=0;
        }
    }
    void update(int tl,int tr,int val,int l=0,int r=mxn-1,int v=1){
        if(r<tl or tr<l){
            return;
        }
        if(tl<=l and r<=tr){
            st[v].mx+=val;
            st[v].add+=val;
            return;
        }
        push(v);
        int mid=(l+r)/2;
        update(tl,min(mid,tr),val,l,mid,v*2);
        update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
        st[v].mx=max(st[v*2].mx,st[v*2+1].mx);
    }
    int find(int tl,int tr,int val,int l=0,int r=mxn-1,int v=1){
        if(r<tl or tr<l){
            return -1;
        }
        if(st[v].mx<val){
            return -1;
        }
        if(l==r){
            return l;
        }
        push(v);
        int mid=(l+r)/2;
        int res=find(tl,min(mid,tr),val,l,mid,v*2);
        if(res!=-1) return res;
        return find(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
    }
};

signed main(){_
    int n,m,q;
    cin>>n>>m>>q;
    struct upd{
        int t,l,k;
        bool operator<(const upd &y)const{
            return l<y.l;
        }
    };
    vector<upd> op;
    vector<int> C(q);
    vector<vector<pair<int,int>>> qs(n+1);
    st1 segtree;
    for(int i=0;i<q;i++){
        //cout<<"i "<<i<<'\n';
        int t;
        cin>>t;
        if(t==1){
            int l,r,c,k;
            cin>>l>>r>>c>>k;
            C[i]=c;
            op.push_back({i,l,k});
            op.push_back({i,r+1,-k});
            segtree.add(l,r,k);
        }
        else if(t==2){
            int l,r,k;
            cin>>l>>r>>k;
            segtree.del(l,r,k);
        }
        else{
            int a,b;
            cin>>a>>b;
            int cnt=segtree.query(a)+b;
            //cout<<"q "<<a<<' '<<i<<' '<<cnt<<'\n';
            qs[a].push_back({i,cnt});
        }
    }
    vector<int> ans(q,-1);
    sort(all(op));
    int pos=0;
    st2 segtree2;
    for(int i=1;i<=n;i++){
        while(pos<(int)op.size() and op[pos].l==i){
            segtree2.update(op[pos].t,q-1,op[pos].k);
            pos++;
        }
        for(auto v:qs[i]){
            int time=segtree2.find(0,v.f,v.s);
            if(time==-1) ans[v.f]=0;
            else ans[v.f]=C[time];
        }
    }
    for(int i=0;i<q;i++){
        if(ans[i]!=-1) cout<<ans[i]<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//diaoborz

Compilation message (stderr)

foodcourt.cpp: In function 'void setIO(std::string)':
foodcourt.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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