Submission #723450

#	Time	Username	Problem	Language	Result	Execution time	Memory
723450		sysia	Food Court (JOI21_foodcourt)	C++17	100 / 100	846 ms	49200 KiB

foodcourt

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

struct TreeSum{
    vector<int>tab;
    int size = 1;

    TreeSum(int n){
        while (size < n) size*=2;
        tab.assign(2*size, 0);
    }

    void update(int l, int r, int v){
        for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
            if (!(l&1)) tab[l+1] += v;
            if (r&1) tab[r-1] += v;
        }
    }

    void clear(){
        tab.assign(2*size, 0);
    }

    int query(int x){
        x += size;
        int ans = 0;
        while (x){
            ans += tab[x];
            x/=2;
        }
        return ans;
    }
};

struct Tree{
    vector<int>tab, lazy;
    int size = 1;

    Tree(int n){
        while (size < n) size*=2;
        tab.assign(2*size, 0);
        lazy.assign(2*size, 0);
    }

    void apply(int x, int a, int c){
        tab[x] = max(tab[x] + a, c);
        lazy[x] += a;
    }

    void push(int x){
        apply(2*x, lazy[x], tab[x]);
        apply(2*x+1, lazy[x], tab[x]);
        lazy[x] = 0;
        tab[x] = -oo;
    }

    int query(int x, int lx, int rx, int pos){
        if (lx == rx) return tab[x];
        push(x);
        int m = (lx+rx)/2;
        if (pos <= m) return query(2*x, lx, m, pos);
        return query(2*x+1, m+1, rx, pos);
    }

    void update(int x, int lx, int rx, int l, int r, int v){
        if (lx > r || rx < l) return;
        if (lx >= l && rx <= r) {
            apply(x, v, -oo);
            return;
        }
        if (lx != rx) push(x);
        int m = (lx+rx)/2;
        update(2*x, lx, m, l, r, v);
        update(2*x+1, m+1, rx, l, r, v);
    }
};

struct TreeMin{
    vector<T>tab;
    vector<int>lazy;
    int size = 1;

    TreeMin(int n){
        while (size < n) size*=2;
        tab.assign(2*size, {oo, oo});
        lazy.assign(2*size, 0);
    }
    
    void set(int x, int lx, int rx, int pos, T val){
        if (lx == rx) {
            tab[x] = val;
            return;
        }
        push(x);
        int m = (lx+rx)/2;
        if (pos <= m) set(2*x, lx, m, pos, val);
        else set(2*x+1, m+1, rx, pos, val);
        tab[x] = min(tab[2*x], tab[2*x+1]);
    }

    void push(int x){
        for (auto k: {2*x, 2*x+1}){
            tab[k].first += lazy[x];
            lazy[k] += lazy[x];
        }
        lazy[x] = 0;
    }

    T query(int x, int lx, int rx, int l, int r){
        if (lx != rx) push(x);
        if (lx > r || rx < l) return {oo, oo};
        if (lx >= l && rx <= r) return tab[x];
        int m = (lx+rx)/2;
        return min(query(2*x, lx, m, l, r), query(2*x+1, m+1, rx, l, r));
    }

    void update(int x, int lx, int rx, int l, int r, int v){
        if (lx != rx) push(x);
        if (lx > r || rx < l) return;
        if (lx >= l && rx <= r){
            
            tab[x].first += v;
            lazy[x] += v;
            debug(lx, rx, v, tab[x]);
            return;
        }
        int m = (lx+rx)/2;
        update(2*x, lx, m, l, r, v);
        update(2*x+1, m+1, rx, l, r, v);
        tab[x] = min(tab[2*x], tab[2*x+1]);
    }
};

void solve(){
    int n, m, q; cin >> n >> m >> q;
    Tree t(n+2);
    TreeSum sum(n+2);
    vector<vector<T>>sweep(n+1);
    vector<tuple<int, int, int, int, int>>groups;
    vector<int>ans(q+1, -1);
    for (int i = 0; i<q; i++){
        int type; cin >> type;
        if (type == 1){
            int l, r, c, k; cin >> l >> r >> c >> k;
            t.update(1, 0, t.size-1, l, r, +k);
            t.apply(1, 0, 0);
            sum.update(l, r, +k);
            groups.emplace_back(i, l, r, c, k);
        } 
        if (type == 2){
            int l, r, k; cin >> l >> r >> k;
            t.update(1, 0, t.size-1, l, r, -k);
            t.apply(1, 0, 0);
        }
        if (type == 3){
            int a, b; cin >> a >> b;
            int present = max(0LL, t.query(1, 0, t.size-1, a));
            int all = sum.query(a);
            int deleted = all - present;
            int now = deleted + b;
            debug(all, present, deleted, now);
            if (b > present) {
                ans[i] = 0;
            } else {
                debug(now, i);
                sweep[a].emplace_back(now, i);
            }
        }
    }
    vector<int>ptr(n+1);
    for (int i = 1; i<=n; i++) {
        sort(sweep[i].begin(), sweep[i].end());
    }
    int ck = 0;
    int last = -1;
    TreeMin tt(n+2);
    for (int i = 1; i<=n; i++){
        if (sweep[i].size()){
            tt.set(1, 0, tt.size-1, i, {sweep[i][0].first, i});
            debug(i, sweep[i][0].first);
        }
    }
    sum.clear();
    auto forward = [&](int i){
        while (ck < (int)groups.size() && get<0>(groups[ck]) <= i){
            auto [ii, l, r, c, k] = groups[ck];
            sum.update(l, r, +k);
            tt.update(1, 0, tt.size-1, l, r, -k);
            debug(l, r, -k);
            last = c;
            ck++;
        }
    };
    for (int rep = 0; rep<=q; rep++){
        forward(rep);
        while (1){
            auto maybe = tt.query(1, 0, tt.size-1, 1, n);
            debug(maybe);
            if (maybe.first > 0) break;
            debug(maybe);
            int i = maybe.second;
            int idx = sweep[i][ptr[i]].second;
            ans[idx] = last;
            debug(idx, last);
            ptr[i]++;
            T now = {oo, oo};
            if (ptr[i] < (int)sweep[i].size()) now = {sweep[i][ptr[i]].first-sum.query(i), i};
            tt.set(1, 0, tt.size-1, i, now);
        }
    }
    for (int i = 0; i<q; i++){
        if (ans[i] != -1){
            cout << ans[i] << "\n";
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    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