Submission #472665

#	Time	Username	Problem	Language	Result	Execution time	Memory
472665		balbit	Food Court (JOI21_foodcourt)	C++14	68 / 100	560 ms	94908 KiB

foodcourt

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

#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define REP(i,n) for(int i = 0; i<n; ++i)
#define pb push_back
#define SZ(x) (int)((x).size())

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S&& ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif

const int N = 250005;
const ll inf = 3e18;

ll bs[N];

void mo(int e, ll v) {
    for(++e; e<N; e+=e&-e) bs[e] += v;
}
ll qu(int e) {
    ll re = 0;
    for(++e; e>0; e-=e&-e) re += bs[e];
    return re;
}

int findfirst(ll cap) {
    int r = 0;
    for (int ty = 1<<__lg(N); ty >= 1; ty >>= 1) {
        if (cap >= bs[r + ty]) {
            r += ty; cap -= bs[r];
        }
    }
    return r;
}

ll s[N*4], mn[N*4], tg[N*4];
ll who[N]; // which group is added at this time

void push(int o, int l, int r) {
    if(tg[o]) {
        s[o] += tg[o];
        mn[o] += tg[o];
        if(l!=r) {
            tg[o*2] += tg[o];
            tg[o*2+1] += tg[o];
        }
        tg[o] = 0;
    }
}

ll QU(int L, int R, int o=1, int l=0, int r=N-1) {
    if(l > R || r<L) return inf;
    push(o,l,r);
    if(l>=L && r <=R) {
        return mn[o];
    }
    int mid = (l+r)/2;
    return min(
               QU(L,R,o*2,l,mid),
               QU(L,R,o*2+1,mid+1,r)
               );
}

ll GET(int p, int o=1, int l=0, int r=N-1) {
    if (l > p || r < p) return -1;
    push(o,l,r);
    if(l==r) return s[o];
    int mid = (l+r)/2;
    return p<=mid?GET(p,o*2,l,mid) : GET(p,o*2+1,mid+1,r);
}

void MO(int L, int R, ll v, int o=1, int l=0, int r = N-1) {
    push(o,l,r);
    if(l > R ||r < L) return;
    if(l>=L && r <=R) {
        tg[o] += v;
        push(o,l,r);
        return;
    }
    int mid = l+r>>1;
    MO(L,R,v,o*2,l,mid);
    MO(L,R,v,o*2+1,mid+1,r);
    s[o] = s[o*2]+s[o*2+1];
    mn[o] = min(mn[o*2], mn[o*2+1]);
}

vector<pii>ev[N]; // {position, value}
vector<pii>ev2[N]; // {position, value}
vector<pii> que[N]; // {position, number};

ll ans[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n,m,q; cin>>n>>m>>q;
    memset(ans, -1, sizeof ans);
    REP(i,q) {
        int tp ;cin>>tp;
        if(tp == 1) {
            ll l,r,c,k; cin>>l>>r>>c>>k;
            who[i] = c;// group set
            ev[l].pb({i,k});
            ev[r+1].pb({i,-k});
        }else if (tp == 2) {
            ll l,r,k; cin>>l>>r>>k;
            ev2[l].pb({i,-k});
            ev2[r+1].pb({i,+k});
        }else if (tp == 3) {
            ll a,b; cin>>a>>b;
            que[a].pb({i, b});
        }
    }

    for(int i=1; i<=n; ++i) {
//        bug("position ", i);
        for(pii p : ev[i]) {
            int at = p.f;
            ll val = p.s;
            MO(at, N-1, val);
            bug(at, val);
            mo(at, val);
        }
        for(pii p : ev2[i]) {
            int at = p.f;
            ll val = p.s;
            MO(at, N-1, val);
            bug(at, val);
        }
        for(pii p : que[i]) {
            int at = p.f;
            ll num = p.s;
            ll low = min(0ll,QU(0, at));
            ll val = GET(at);
            bug(val, low);
            if (val - low >= num) {
                // continue here
                bug(num, val-low-num);
                num = val - low + 1 - num;

                int pp = findfirst(qu(at) - num);

                bug(pp);
                ans[at] = who[pp];
            }else{
                ans[at] = 0;
            }
        }
    }
    REP(i, q) {
        if (ans[i] != -1) cout<<ans[i]<<endl;
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'void MO(int, int, long long int, int, int, int)':
foodcourt.cpp:90:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     int mid = l+r>>1;
      |               ~^~

• 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