Submission #389121

#	Time	Username	Problem	Language	Result	Execution time	Memory
389121		couplefire	Food Court (JOI21_foodcourt)	C++17	100 / 100	748 ms	56348 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define MAXN 262144
#define INF 1000000000000000009ll

struct node{
    long long psum = 0, nsum = 0;
    pair<long long, int> minsum = {0, -1};
    node(){}
};

node tree[2*MAXN];

void build(int v = 1, int tl = 0, int tr = MAXN-1){
    tree[v].minsum.second = tl;
    if(tl == tr) return;
    int tm = (tl+tr)/2;
    build(v*2, tl, tm); build(v*2+1, tm+1, tr);
}

void upd(int id, long long val, int v = 1, int tl = 0, int tr = MAXN-1){
    if(tl > id || tr < id) return;
    if(tl == tr){
        if(val > 0) tree[v].psum = val, tree[v].nsum = 0;
        else tree[v].nsum = -val, tree[v].psum = 0;
        tree[v].minsum.first = val;
        return;
    }
    int tm = (tl+tr)/2;
    upd(id, val, v*2, tl, tm); upd(id, val, v*2+1, tm+1, tr);
    tree[v].psum = tree[2*v].psum + tree[2*v+1].psum;
    tree[v].nsum = tree[2*v].nsum + tree[2*v+1].nsum;
    tree[v].minsum = min(tree[2*v].minsum, {tree[2*v+1].minsum.first+tree[2*v].psum-tree[2*v].nsum, tree[v*2+1].minsum.second});
}

pair<long long, int> getminsum(int l, int r, long long cursum = 0, int v = 1, int tl = 0, int tr = MAXN-1){
    if(tl > r || tr < l) return {INF, -1};
    if(l <= tl && tr <= r) return {tree[v].minsum.first+cursum, tree[v].minsum.second};
    int tm = (tl+tr)/2;
    return min(getminsum(l, r, cursum, v*2, tl, tm), getminsum(l, r, cursum + tree[v*2].psum - tree[2*v].nsum, v*2+1, tm+1, tr));
}

long long getnsum(int l, int r, int v = 1, int tl = 0, int tr = MAXN-1){
    if(tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return tree[v].nsum;
    int tm = (tl+tr)/2;
    return getnsum(l, r, v*2, tl, tm) + getnsum(l, r, v*2+1, tm+1, tr);
}

long long getpsum(int l, int r, int v = 1, int tl = 0, int tr = MAXN-1){
    if(tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return tree[v].psum;
    int tm = (tl+tr)/2;
    return getpsum(l, r, v*2, tl, tm) + getpsum(l, r, v*2+1, tm+1, tr);
}

int getans(long long k, int v = 1, int tl = 0, int tr = MAXN-1){
    if(tl == tr){
        if(tree[v].psum >= k) return tl;
        return MAXN;
    }
    int tm = (tl+tr)/2;
    if(tree[2*v].psum >= k) return getans(k, v*2, tl, tm);
    return getans(k-tree[2*v].psum, v*2+1, tm+1, tr);
}

int n, m, q;
int color[MAXN], ans[MAXN];
vector<pair<long long, int>> ask[MAXN];
vector<pair<long long, int>> add[MAXN];
vector<pair<long long, int>> del[MAXN];

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    build();
    cin >> n >> m >> q;
    for(int i = 1; i<=q; i++){
        int t; cin >> t;
        if(t == 1){
            int l, r, c; long long k; cin >> l >> r >> c >> k;
            add[l].push_back({k, i});
            del[r+1].push_back({k, i});
            color[i] = c;
        }
        else if(t == 2){
            int l, r; long long k; cin >> l >> r >> k;
            add[l].push_back({-k, i});
            del[r+1].push_back({-k, i});
        }
        else{
            int a; long long b; cin >> a >> b;
            ask[a].push_back({b, i});
        }
    }
    for(int i = 1; i<=n; i++){
        for(auto x : del[i]) upd(x.second, 0);
        for(auto x : add[i]) upd(x.second, x.first);
        for(auto x : ask[i]){
            int l = getminsum(0, x.second).second+1, r = x.second;
            long long k = x.first+getpsum(0, l-1)+getnsum(l, r);
            // cerr << "hi: " << getpsum(0, 1) << endl;
            int res = getans(k);
            if(res > x.second) ans[x.second] = -1;
            else ans[x.second] = color[res];
        }
    }
    for(int i = 1; i<=q; i++){
        if(ans[i] == 0) continue;
        cout << (ans[i] == -1?0:ans[i]) << endl;
    }
}

• 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