Submission #421818

#	Time	Username	Problem	Language	Result	Execution time	Memory
421818		tqbfjotld	Food Court (JOI21_foodcourt)	C++14	7 / 100	1075 ms	113672 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define int long long


struct node{
    int s,e;
    int lazymin,lazych;
    int v;
    node *l,*r;
    node (int _s, int _e){
        s = _s; e = _e;
        lazymin = 0; lazych = 0;
        v = 0;
        if (s!=e){
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
        }
    }
    void proc(){
        if (lazymin==0 && lazych==0) return;
        if (s!=e){
            l->lazymin = min(l->lazymin,l->lazych+lazymin);
            l->lazych += lazych;
            r->lazymin = min(r->lazymin,r->lazych+lazymin);
            r->lazych += lazych;
        }
        if (s==e){
            v += lazymin;
            v = max(v,0LL);
            v -= lazymin;
            v += lazych;
        }
        lazymin = 0;
        lazych = 0;
    }
    void inc(int a, int b, int val){
        proc();
        if (a<=s && e<=b){
            lazych += val;
            proc();
            return;
        }
        else if (b<=(s+e)/2){
            l->inc(a,b,val);
        }
        else if (a>(s+e)/2){
            r->inc(a,b,val);
        }
        else{
            l->inc(a,b,val);
            r->inc(a,b,val);
        }
        l->proc();
        r->proc();
    }
    void dec(int a, int b, int val){
        proc();
        if (a<=s && e<=b){
            lazych -= val;
            lazymin = min(lazymin,lazych);
            proc();
            return;
        }
        else if (b<=(s+e)/2){
            l->dec(a,b,val);
        }
        else if (a>(s+e)/2){
            r->dec(a,b,val);
        }
        else{
            l->dec(a,b,val);
            r->dec(a,b,val);
        }
        l->proc(); r->proc();
    }
    int qu(int pos){
        proc();
        if (s==e) return v;
        if (pos>(s+e)/2)return r->qu(pos);
        else return l->qu(pos);
    }
}*root;

struct q_dat{
    int l,r;
    int t,k;
    q_dat(){
        l = 0; r = 0; t = 0; k = 0;
    }
    q_dat(int _l, int _r, int _t, int _k){
        l = _l; r = _r; t = _t; k = _k;
    }
};
vector<q_dat> query1;
int groupnum[250005];
vector<q_dat> query2;
vector<pair<pair<int,int>,int> > query3;

int fw[250005];

void upd(int pos, int val){
    while (pos<250005){
        fw[pos] += val;
        pos+=pos&-pos;
    }
}
int qu(int pos){
    int ans = 0;
    while (pos>0){
        ans += fw[pos];
        pos -= pos&-pos;
    }
    return ans;
}

int numt[250005];
int ans[250005];
vector<pair<pair<int,int>,int> > bsvals[250005];
vector<pair<pair<int,int>,int> > bsvals2[250005];

struct node2{
    int s, e;
    int lazyval;
    node2 *l,*r;
    node2 (int _s, int _e){
        s = _s; e = _e;
        lazyval = -1;
        if (s!=e){
            l = new node2(s,(s+e)/2);
            r = new node2((s+e)/2+1,e);
        }
    }
    void proc(){
        if (lazyval==-1) return;
        if (s!=e){
            l->lazyval = lazyval;
            r->lazyval = lazyval;
            lazyval = -1;
        }
    }
    int qu(int pos){
        proc();
        if (s==e) return lazyval;
        if (pos<=(s+e)/2) return l->qu(pos);
        return r->qu(pos);
    }
    void upd(int a, int b, int val){
        proc();
        if (a<=s && e<=b) {
            lazyval = val;
            proc();
            return;
        }
        if (b<=(s+e)/2){
            l->upd(a,b,val);
        }
        else if (a>(s+e)/2){
            r->upd(a,b,val);
        }
        else{
            l->upd(a,b,val);
            r->upd(a,b,val);
        }
    }
}*root2;

int incl[250005];
int incr[250005];
int incamt[250005];
int finans[250005];

main(){
    int n,m,q;
    scanf("%lld%lld%lld",&n,&m,&q);
    root = new node(1,n);
    for (int x = 0; x<q; x++){
        int a;
        scanf("%lld",&a);
        if (a==1){
            int b,c,d,e;
            scanf("%lld%lld%lld%lld",&b,&c,&d,&e);
            groupnum[x] = d;
            query1.push_back(q_dat(b,c,x,e));
            root->inc(b,c,e);
            upd(b,e);
            upd(c+1,-e);
            incl[x] = b;
            incr[x] = c;
            incamt[x] = e;
        }
        else if (a==2){
            int b,c,d;
            scanf("%lld%lld%lld",&b,&c,&d);
            query2.push_back(q_dat(b,c,x,d));
            root->dec(b,c,d);
        }
        else if (a==3){
            int b,c;
            scanf("%lld%lld",&b,&c);
            query3.push_back({{b,c},x});
            int num = root->qu(b);
            numt[x] = qu(b)-num+c;
            incl[x] = b;
            if (num<c){
                ans[x] = -1;
            }
            //printf("%lld has %lld\n",b,numpopped[x]);
        }
    }
    for (auto x : query3){
        if (ans[x.second]==-1) continue;
        int a = -1;
        int b = q-1;
        int mid = (a+b)/2;
        bsvals[mid].push_back({{a,b},x.second});
    }
    bool found = true;
    while (found){
        found = false;
        for (int k = 0; k<250005; k++){
            fw[k] = 0;
        }
        for (int t = 0; t<q; t++){
            if (incamt[t]!=0){
                upd(incl[t],incamt[t]);
                upd(incr[t]+1,-incamt[t]);
            }
            for (auto x : bsvals[t]){
                if (x.first.first+1==x.first.second) {
                    ans[x.second] = x.first.second;
                    continue;
                }
                if (qu(incl[x.second])>=numt[x.second]){
                    bsvals2[(x.first.first+t)/2].push_back({{x.first.first,t},x.second});
                }
                else{
                    bsvals2[(x.first.second+t)/2].push_back({{t,x.first.second},x.second});
                }
                found = true;
            }
            bsvals[t].clear();
        }
        swap(bsvals2,bsvals);
    }
    root2 = new node2(1,n);
    vector<pair<pair<int,int>,int> > stuff;
    for (auto x : query3){
        if (ans[x.second]==-1) {
            continue;
        }
        stuff.push_back({{ans[x.second],incl[x.second]},x.second});
    }
    sort(stuff.begin(),stuff.end());
    int curt = 0;
    for (auto x : stuff){
        while (curt<=x.first.first){
            if (incamt[curt]!=0){
                root2->upd(incl[curt],incr[curt],curt);
                //printf("set %lld to %lld with %lld\n",incl[curt],incr[curt],curt);
            }
            curt++;
        }
        finans[x.second] = root2->qu(x.first.second);
        //printf("query %lld = %lld\n",x.first.second,finans[x.second]);
    }
    for (auto x : query3){
       // printf("ans = %lld\n",ans[x.second]);
        if (finans[x.second]==0){
            printf("0\n");
        }
        else
        printf("%lld\n",groupnum[finans[x.second]]);
    }
}

Compilation message (stderr)

foodcourt.cpp:173:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  173 | main(){
      | ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |     scanf("%lld%lld%lld",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         scanf("%lld",&a);
      |         ~~~~~^~~~~~~~~~~
foodcourt.cpp:182:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |             scanf("%lld%lld%lld%lld",&b,&c,&d,&e);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:194:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |             scanf("%lld%lld%lld",&b,&c,&d);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:200:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |             scanf("%lld%lld",&b,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

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