Submission #994963

#	Time	Username	Problem	Language	Result	Execution time	Memory
994963		snpmrnhlol	Food Court (JOI21_foodcourt)	C++17	68 / 100	1074 ms	45660 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 25e4;
struct nod{
    ll lazysum2;
    ll lazysum,lazymn;
}seg[4*N];
bool ok[N];
ll rem[N],val[N];
ll n,m,q;
ll qcnt = 0,updcnt = 0;
vector <pair<ll,ll>> queries[N];
vector <ll> updates[N + 1];
pair<ll,ll> updates2[N];
ll ans[N];
void push(ll node, ll l, ll r){
    if(l != r){
        seg[node*2].lazysum2+=seg[node].lazysum2;
        seg[node*2 + 1].lazysum2+=seg[node].lazysum2;
        seg[node*2].lazymn = min(seg[node*2].lazymn,seg[node*2].lazysum + seg[node].lazymn);
        seg[node*2 + 1].lazymn = min(seg[node*2 + 1].lazymn,seg[node*2 + 1].lazysum + seg[node].lazymn);
        seg[node*2].lazysum+=seg[node].lazysum;
        seg[node*2 + 1].lazysum+=seg[node].lazysum;
    }else{
        val[l]+=seg[node].lazysum2;
        if(rem[l] + seg[node].lazymn <= 0){
            rem[l] = seg[node].lazysum - seg[node].lazymn;
        }else{
            rem[l]+=seg[node].lazysum;
        }
    }
    seg[node].lazysum2 = 0;
    seg[node].lazysum = 0;
    seg[node].lazymn = 0;
}
void upd(ll ql, ll qr, ll x, ll l = 0, ll r = n - 1, ll node = 1){
    push(node,l,r);
    if(ql <= l && r <= qr){
        seg[node].lazysum+=x;
        if(x >= 0)seg[node].lazysum2+=x;
        seg[node].lazymn = min(seg[node].lazymn,seg[node].lazysum);
    }else{
        ll mij = (l + r)/2;
        if(qr <= mij){
            upd(ql,qr,x,l,mij,node*2);
        }else if(mij + 1 <= ql){
            upd(ql,qr,x,mij + 1,r,node*2 + 1);
        }else{
            upd(ql,qr,x,l,mij,node*2);
            upd(ql,qr,x,mij + 1,r,node*2 + 1);
        }
    }
}
void get(ll pos,ll l = 0,ll r = n - 1,ll node = 1){
    push(node,l,r);
    if(l != r){
        ll mij = (l + r)/2;
        if(pos <= mij){
            return get(pos,l,mij,node*2);
        }else{
            return get(pos,mij + 1,r,node*2 + 1);
        }
    }
}
void upd2(ll pos){
    ok[pos]^=1;
}
ll get2(ll x){
    for(ll i = 0;i < updcnt;i++){
        if(ok[i]){
            //cout<<"query\n"<<x<<'\n';;
            //cout<<updates2[i].first<<' '<<updates2[i].second<<'\n';
            x-=updates2[i].second;
            if(x <= 0)return updates2[i].first;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
    for(ll i = 0;i < q;i++){
        ll tip;
        cin>>tip;
        if(tip == 1){
            ll l,r,c,k;
            cin>>l>>r>>c>>k;
            l--;r--;
            upd(l,r,k);
            updates2[updcnt] = {c,k};
            updates[l].push_back(updcnt);
            updates[r + 1].push_back(updcnt);
            updcnt++;
        }else if(tip == 2){
            ll l,r,k;
            cin>>l>>r>>k;
            l--;r--;
            upd(l,r,-k);
        }else{
            ll a,b;
            cin>>a>>b;
            a--;
            get(a);
            //cout<<"update:"<<val[a]<<' '<<rem[a]<<'\n';
            if(rem[a] < b){
                ans[qcnt++] = 0;
                //cout<<ans[qcnt - 1]<<'\n';
            }else{
                queries[a].push_back({qcnt++,b + val[a] - rem[a]});
                //cout<<b + val[a] - rem[a]<<"th customer from"<<a<<'\n';
            }
        }
    }
    for(ll i = 0;i < n;i++){
        for(auto j:updates[i]){
            upd2(j);
        }
        for(auto j:queries[i]){
            ans[j.first] = get2(j.second);
        }
    }
    for(ll i = 0;i < qcnt;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}
/**
3 5 5
1 2 3 5 2
1 1 2 2 4
2 1 3 3
1 2 3 4 2
3 3 2
**/

Compilation message (stderr)

foodcourt.cpp: In function 'll get2(ll)':
foodcourt.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^

• 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