Submission #978234

#	Time	Username	Problem	Language	Result	Execution time	Memory
978234		hotboy2703	Food Court (JOI21_foodcourt)	C++17	100 / 100	374 ms	60488 KiB

foodcourt

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN=2.5e5;
struct node{
    ll sum,worst,cus;
    node(ll a=0,ll b=0,ll c=0):sum(a),worst(b),cus(c){

    }

};
node operator + (const node &x,const node &y){
    node res;
    res.sum = x.sum+y.sum;
    res.worst = min(x.worst,y.worst+x.sum);
    res.cus = x.cus+y.cus;
    return res;
}

node tree[MAXN*4+100];

void update(ll id,ll l,ll r,ll i,node v){
    if (l > i || r < i)return;
    if (l == r){tree[id]=v;return;}
    ll mid = (l + r) >> 1;
    update(id<<1,l,mid,i,v);
    update(id<<1|1,mid+1,r,i,v);
    tree[id] = tree[id<<1]+tree[id<<1|1];
}
node get(ll id,ll l,ll r,ll l1,ll r1){
    if (l > r1 || l1 > r || l1 > r1)return node(0,0,0);
    if (l1 <= l && r <= r1)return tree[id];
    ll mid = (l + r) >> 1;
    return get(id<<1,l,mid,l1,r1) + get(id<<1|1,mid+1,r,l1,r1);
}
ll get_cus(ll id,ll l,ll r,ll k){
    if (l==r)return l;
    ll mid = (l + r) >> 1;
    if (tree[id<<1].cus >= k)return get_cus(id<<1,l,mid,k);
    else return get_cus(id<<1|1,mid+1,r,k-tree[id<<1].cus);
}
struct query{
    ll x,id;
    node v;
};
void out(ll id,ll l,ll r){
    cout<<id<<' '<<l<<' '<<r<<" : "<<tree[id].sum<<' '<<tree[id].worst<<' '<<tree[id].cus<<'\n';
    if (l != r){
        ll mid = (l + r) >> 1;
        out(id<<1,l,mid);
        out(id<<1|1,mid+1,r);
    }
}
vector <pll> question[MAXN+100];
ll ans[MAXN+100];
ll customer_type[MAXN+100];
ll n,m,q;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>m>>q;
    vector <query> all;
    for (ll i = 1;i <= q;i ++){
        ans[i] = -1;
        ll t,l,r,k,c;
        cin>>t;
        if (t==1){
            cin>>l>>r>>c>>k;
            all.push_back({l,i,node(k,0,k)});
            all.push_back({r+1,i,node(0,0,0)});
            customer_type[i] = c;
        }
        if (t==2){
            cin>>l>>r>>k;
            all.push_back({l,i,node(-k,-k,0)});
            all.push_back({r+1,i,node(0,0,0)});
        }
        if (t==3){cin>>l>>r;question[l].push_back(MP(r,i));}
    }
    sort(all.begin(),all.end(),[&](query x,query y){return x.x < y.x;});
    for (ll i = 1,ptr = 0;i <= n;i ++){
        while (ptr < sz(all) && all[ptr].x<=i){
            update(1,1,q,all[ptr].id,all[ptr].v);
            ptr++;
        }
//        cout<<"SHOP "<<i<<endl;
//        out(1,1,q);
        for (auto x:question[i]){
            node tmp = get(1,1,q,1,x.se);
            if (x.fi > tmp.sum - tmp.worst)ans[x.se] = 0;
            else ans[x.se] = customer_type[get_cus(1,1,q,tmp.cus - (tmp.sum - tmp.worst) + x.fi)];
        }
    }
    for (ll i = 1;i <= q;i++){
        if (ans[i] != -1)cout<<ans[i]<<'\n';
    }
    return 0;
}

• 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