제출 #421865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421865		tqbfjotld	푸드 코트 (JOI21_foodcourt)	C++14	68 / 100	1022 ms	98124 KiB

foodcourt

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

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


//vector<q_dat> query1;
int groupnum[250005];
//vector<q_dat> query2;
vector<pair<pair<int,int>,int> > query3;

int fw[250005];

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

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

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

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

inline void scan(int &a){
    a = 0;
    char ch = ' ';
    while (ch<'0' || ch>'9') ch = getchar();
    while (ch>='0' && ch<='9'){
        a = (a<<3)+(a<<1)+ch-'0';
        ch = getchar();
    }
}

main(){
    int n,m,q;
    scan(n); scan(m); scan(q);
    root = new node(1,n);
    for (int x = 0; x<q; x++){
        int a;
        scan(a);
        if (a==1){
            int b,c,d,e;
            scan(b); scan(c); scan(d); scan(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;
            scan(b); scan(c); scan(d);
           // query2.push_back(q_dat(b,c,x,d));
            root->dec(b,c,d);
        }
        else if (a==3){
            int b,c;
            scan(b); scan(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 = x.second;
        int mid = (a+b)/2;
        bsvals[mid].push_back({{a,b},x.second});
    }
    bool found = true;
    while (found){
        found = false;
        for (int32_t k = 0; k<250005; k++){
            fw[k] = 0;
        }
        for (int32_t 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 (ans[x.second]==-1){
            printf("0\n");
        }
        else{
            assert(finans[x.second]!=-1);
            printf("%lld\n",groupnum[finans[x.second]]);
        }

    }
}

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp:171:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  171 | main(){
      | ^~~~

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