Submission #386552

#	Time	Username	Problem	Language	Result	Execution time	Memory
386552		PurpleCrayon	Food Court (JOI21_foodcourt)	C++17	100 / 100	850 ms	47820 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define sz(v) int(v.size())
#define ar array
const int MAXN = 2.5e5+10, MAXQ = 2.5e5+10, MAXL = 18;
const ll INF = 1e18;

struct Beats {
    int n;
    void init(int _n){ n=_n; }

    struct info {
        ll lzy_ad=0, lzy_mx=-INF, lzy_ad2=0;
    } t[4*MAXN];

    void push(int v, int tl, int tr){
        if (tl == tr) return;

        t[2*v].lzy_ad += t[v].lzy_ad;
        t[2*v+1].lzy_ad += t[v].lzy_ad;
        t[2*v].lzy_mx += t[v].lzy_ad;
        t[2*v+1].lzy_mx += t[v].lzy_ad;

        t[2*v].lzy_mx = max(t[2*v].lzy_mx, t[v].lzy_mx);
        t[2*v+1].lzy_mx = max(t[2*v+1].lzy_mx, t[v].lzy_mx);

        t[2*v].lzy_ad2 += t[v].lzy_ad2;
        t[2*v+1].lzy_ad2 += t[v].lzy_ad2;

        t[v].lzy_ad = t[v].lzy_ad2 = 0, t[v].lzy_mx = -INF;
    }
    void upd(int v, int tl, int tr, int l, int r, ll val){
        push(v, tl, tr);
        if (l <= tl && tr <= r) {
            t[v].lzy_ad += val, t[v].lzy_mx += val;
            if (val > 0) t[v].lzy_ad2 += val;
            return;
        }
        int tm=(tl+tr)/2;
        if (l <= tm)
            upd(2*v, tl, tm, l, r, val);
        if (r > tm)
            upd(2*v+1, tm+1, tr, l, r, val);
    }
    ll qry(int v, int tl, int tr, int pos){
        push(v, tl, tr);
        if (tl == tr){
            return t[v].lzy_ad2 - max(t[v].lzy_ad, t[v].lzy_mx);
        }
        int tm=(tl+tr)/2;
        if (pos <= tm) return qry(2*v, tl, tm, pos);
        else return qry(2*v+1, tm+1, tr, pos);
    }

    void ad(int l, int r, ll val){ upd(1, 0, n-1, l, r, val); }
    void fix(){ t[1].lzy_mx = max(t[1].lzy_mx, 0ll); }
    ll qry(int i){ return qry(1, 0, n-1, i); }
} bst;

struct FT {
    int n;
    ll bit[MAXN];

    void init(int _n){ n=_n+10; memset(bit, 0, sizeof(bit)); }
    void add(int idx, ll val) {
        for (++idx; idx < n; idx += idx & -idx)
            bit[idx] += val;
    }
    void upd(int l, int r, ll val) {
        add(l, val);
        add(r+1, -val);
    }
    ll qry(int idx) {
        ll ret = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }
} st;

int n, m, q, bl[MAXQ], br[MAXQ];
ar<ll, 2> qv[MAXQ];
ar<ll, 4> qu[MAXQ];
vector<int> check[MAXQ];

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> q;
    
    bst.init(n);

    fill(qv, qv+q, ar<ll, 2>{-1, -1});
    fill(qu, qu+q, ar<ll, 4>{-1, -1, -1, -1});
    for (int qt = 0; qt < q; qt++){
        int ty; cin >> ty;

        if (ty == 1){ //add
            int l, r, c; ll k; cin >> l >> r >> c >> k, --l, --r;
            qu[qt] = {l, r, c, k};
            bst.ad(l, r, k);
        } else if (ty == 2){ //remove
            int l, r; ll val; cin >> l >> r >> val, --l, --r;
            bst.ad(l, r, -val);
            bst.fix();
        } else if (ty == 3){ //qry
            int i; ll v; cin >> i >> v, --i;
            qv[qt] = {i, bst.qry(i)+v};
        } else assert(false);
    }
    
    //for (int i = 0; i < q; i++) if (qv[i][0] != -1) cerr << qv[i][0] << ' ' << qv[i][1] << endl;

    fill(bl, bl+q, -1);
    fill(br, br+q, q);
    for (int rep = 0; rep < MAXL; rep++){
        st.init(n);
        for (int i = 0; i < q; i++) if (qv[i][0] != -1) {
            int mid = (bl[i]+br[i])/2;
            if (bl[i] < mid && mid < br[i])
                check[mid].push_back(i);
        }
        for (int i = 0; i < q; i++) {
            if (qu[i][0] != -1)
                st.upd(qu[i][0], qu[i][1], qu[i][3]);
            for (int v : check[i]) {
                if (st.qry(qv[v][0]) >= qv[v][1]) {
                    br[v] = i;
                } else {
                    bl[v] = i;
                }
            }
            vector<int>().swap(check[i]);
        } 
    }
    for (int i = 0; i < q; i++) if (qv[i][0] != -1) {
        int ca = br[i];
        cout << (ca>=i?0:qu[ca][2]) << '\n';
    }
}

• 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