Submission #831721

#	Time	Username	Problem	Language	Result	Execution time	Memory
831721		Ronin13	Food Court (JOI21_foodcourt)	C++17	24 / 100	530 ms	84120 KiB

foodcourt

#include <bits/stdc++.h>
#define ll long long  
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 250001;

struct node{
    ll sum, mn;
    ll sum1, sum2;
    int ind;
    node(){
        sum = mn = sum1 = 0;
        ind = 0;
        sum2 = 0;
    }
    node(int val){
        mn = min(0, val);
        sum = sum1 = val;
    }
}t[4 * nmax];

node merg(node a, node b){
    node c;
    c.sum = a.sum + b.sum;
    c.sum1 = a.sum1 + b.sum1;
    c.sum2 = a.sum2 + b.sum2;
    if(a.mn <= a.sum + b.mn){
        c.mn = a.mn;
        c.ind = a.ind;
    }
    else{
        c.mn = a.sum + b.mn;
        c.ind = b.ind;
    }
    return c;
}

void add(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v].sum = val;
        t[v].mn = val;
        t[v].sum1 = val;
        return;
    }
    int m = (l + r) / 2;
    add(2 * v, l,m, pos, val);
    add(2 *  v + 1, m + 1, r, pos, val);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}

void rem(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v].sum = -val;
        t[v].mn = -val;
        t[v].sum2 = val;
        return;
    }
    int m = (l + r) / 2;
    rem(2 * v,l, m, pos, val);
    rem(2 * v + 1, m + 1, r, pos, val);
    t[v] = merg(t[2 * v], t[2 * v +  1]);
}


node get_mn(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return {0};
    if(l >= st && r <= fin){
        return t[v];
    }
    int m = (l + r) / 2;
    return merg(get_mn(2 * v, l, m, st, fin),
                    get_mn(2 * v + 1, m + 1, r, st, fin));
}


ll get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st){
        return 0;
    }
    if(l >= st && r <= fin){
        return t[v].sum1;
    }
    int m = (l + r) / 2;
    return get(2 * v, l, m, st, fin) + get(2 * v + 1,m + 1, r, st, fin);
}
ll get1(int v, int l, int r, int st, int fin){
    if(l > fin || r < st)
        return 0;
    if(l >= st && r <= fin){
        return t[v].sum2;
    }
    int m = (l + r) / 2;
    return get1(2 * v, l, m, st, fin) + 
            get1(2 * v + 1, m + 1, r, st, fin);
}

int getfirst(int v, int l, int r, int st, int fin, ll val){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin){
        if(t[v].sum1 >= val) {
            while(l != r){
                int m = (l + r) / 2;
                if(t[v * 2].sum1 >= val) v *= 2, r = m;
                else val -= t[2 * v].sum1, v = v * 2 + 1, l = m + 1;
            }
            return l;
        }
        return 0;
    }
    int m = (l + r) / 2;
    int x = getfirst(2 * v, l, m, st, fin, val);
    if(x) return x;
    return getfirst(2 * v + 1, m + 1, r, st, fin, val - t[2 * v].sum1);
}

void build(int v, int l, int r){
    if(l == r){
        t[v].ind = l;
        return;
    }
    int m = (l + r)/ 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
}


int main(){
    int n, m, q; cin >> n >> m >> q;
    build(1, 1, q + 1);
    add(1, 1, q + 1, 1, 0);
    vector <vector <pair<int, int> > > in(n + 1);
    vector <vector <pair<int, int> > > out(n + 1);
    vector <vector <pii> > uu(n + 1);
    vector <vector <pii> > vv(n + 1);
    vector <vector <pii> > qv(n + 1);
    int Val[q + 1];
   vector <pll> ans;
    for(int i = 1; i <= q; i++){
        int t; cin >> t;
        if(t == 1){
            ll a, b, c; cin >> a >> b >> c;
            ll d; cin >> d;
            Val[i] = c;
            in[a].pb({d, i});
            out[b].pb({d, i});
        }
        if(t == 2){
            ll a, b, c; cin >> a >> b >> c;
            uu[a].pb({c, i});
            vv[b].pb({0, i});
        }
        if(t == 3){
            int p; cin >> p;
            ll b; cin >> b;
            qv[p].pb({i, b});
        }
    }
    q++;
    for(int i = 1; i <= n; ++i){
        for(auto to : in[i]){
            add(1, 1, q, to.s + 1, to.f);
        }
        for(auto to : uu[i]){
            rem(1, 1, q, to.s + 1, to.f);
        }
        for(auto to : qv[i]){
            node x = get_mn(1, 1, q, 1, to.f);
            //cout << x.ind << "\n";
            ll sum = get(1, 1, q, 1, x.ind);
            ll val = get1(1, 1, q, x.ind + 1, to.f);
            int pp = getfirst(1, 1, q, x.ind, to.f, val + sum + to.s);
            if(pp > 1){
                ans.pb({to.f, Val[pp - 1]});
            }
            else ans.pb({to.f, 0});
        }
        for(auto to : out[i]){
            add(1, 1, q, to.s + 1, 0);
        }
        for(auto to : vv[i]){
            rem(1, 1, q, to.s + 1, 0);
        }
    }
    sort(ans.begin(), ans.end());
    for(auto to : ans){
        cout << to.s << "\n";
    }
    return 0;
}

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