제출 #503517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503517		cig32	푸드 코트 (JOI21_foodcourt)	C++17	100 / 100	924 ms	115208 KiB

foodcourt

#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
#define int long long
 
const int MAXN = 2.5e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
    int u = uniform_int_distribution<int>(x, y)(rng);
    return u;
}
int N, M, Q;
struct segtree_purq {
    //point update range query version 4
    //Supports:
    //Point update (add)
    //Range sum queries
    //prefix "maximum sum suffix" queries
    struct node {
        long long sum = 0;
        long long mss = 0; 
        long long idx;
    };
    vector<node> a;
    int stok;
    void bu(int l, int r, int idx) {
        if(l == r) {
            a[idx].idx = l;
            return;
        }
        int mid = (l + r) >> 1;
        bu(l, mid, 2*idx+1);
        bu(mid+1, r, 2*idx+2);
        a[idx].idx = a[2*idx+1].idx;
    }
    void u(int l, int r, int tar, int idx, long long val) {
        if(l == r) {
            a[idx].sum += val;
            a[idx].mss = max(0ll, a[idx].sum);
            a[idx].idx = (a[idx].sum >= 0 ? l : -1);
            return;
        }
        int mid = (l + r) >> 1;
        if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
        else u(mid+1, r, tar, 2*idx+2, val);
        a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
        a[idx].mss = max(a[2*idx+2].mss, a[2*idx+1].mss + a[2*idx+2].sum);
        a[idx].idx = (a[2*idx+1].mss + a[2*idx+2].sum > a[2*idx+2].mss ?
                      a[2*idx+1].idx : a[2*idx+2].idx);
    }
    long long qu1(int l, int r, int constl, int constr, int idx) {
        if(l <= constl && constr <= r) return a[idx].sum;
        int mid = (constl + constr) >> 1;
        if(mid < l || r < constl) {
            return qu1(l, r, mid+1, constr, 2*idx+2);
        }
        else if(constr < l || r < mid+1) {
            return qu1(l, r, constl, mid, 2*idx+1);
        }
        else {
            return qu1(l, r, constl, mid, 2*idx+1) + qu1(l, r, mid+1, constr, 2*idx+2);
        }
    }
    pair<pair<long long, int>, long long> qu2(int r, int constl, int constr, int idx) {
        if(constr <= r) {
            return {{a[idx].mss, a[idx].idx}, a[idx].sum};
        }
        int mid = (constr + constl) >> 1;
        if(r < constl) return qu2(r, mid+1, constr, 2*idx+2);
        else if(r < mid+1) return qu2(r, constl, mid, 2*idx+1);
        else {
            pair<pair<long long, int>, long long> rel = qu2(r, constl, mid, 2*idx+1);
            pair<pair<long long, int>, long long> rer = qu2(r, mid+1, constr, 2*idx+2);
            pair<pair<long long, int>, long long> res;
            if(rer.second + rel.first.first > rer.first.first) {
                res.first.first = rer.second + rel.first.first;
                res.first.second = rel.first.second;
            }
            else {
                res.first.first = rer.first.first;
                res.first.second = rer.first.second;
            }
            res.second = rel.second + rer.second;
            return res;
        }
    }
    public:
    void resize(int k) {
        stok = k;
        a.resize(4*k + 10);
        bu(1, stok, 0);
    }
    void update(int i, long long v) {
        u(1, stok, i, 0, v);
    }
    long long query_sum(int l, int r) {
        return qu1(l, r, 1, stok, 0);
    }
    long long query_mss(int r) {
        return qu2(r, 1, stok, 0).first.first;
    }
    long long query_mss_index(int r) {
        return qu2(r, 1, stok, 0).first.second;
    }
};
struct qry {
    int t = 0, l = 0, r = 0, c = 0, k = 0, a = 0, b = 0;
};
void solve(int tc) {
    cin >> N >> M >> Q;
    segtree_purq st, pos, neg; // main, helper
    qry b[Q+1];
    vector<pair<int, int> > delta[N+2];
    vector<pair<int, int> > oh[N+1];
    for(int i=1; i<=Q; i++) {
        cin >> b[i].t;
        if(b[i].t == 1) cin >> b[i].l >> b[i].r >> b[i].c >> b[i].k;
        if(b[i].t == 2) cin >> b[i].l >> b[i].r >> b[i].k;
        if(b[i].t == 3) cin >> b[i].a >> b[i].b;
        if(b[i].t == 1) {
            delta[b[i].l].push_back({i, b[i].k});
            delta[b[i].r + 1].push_back({i, -b[i].k});
        }
        if(b[i].t == 2) {
            delta[b[i].l].push_back({i, -b[i].k});
            delta[b[i].r + 1].push_back({i, b[i].k});
        }
        if(b[i].t == 3) {
            oh[b[i].a].push_back({i, b[i].b});
        }
    }
    st.resize(Q);
    pos.resize(Q);
    neg.resize(Q);
    for(int i=1; i<=N; i++) {
        
        for(pair<int, int> x : delta[i]) {
            st.update(x.first, x.second);
            if(b[x.first].t == 1) {
                pos.update(x.first, x.second);
            }
            if(b[x.first].t == 2) {
                neg.update(x.first, -x.second);
            }
        }
        for(pair<int, int> x : oh[i]) {
            int tot = st.query_mss(x.first);
            int lb = st.query_mss_index(x.first);
            int rb = x.first;
            int stolb = lb; // for reference use
            if(tot == 0) {
                b[x.first].k = 0;
                continue;
            }
            if(lb > rb) {
                continue;
            }
//            assert(lb <= rb);
            int nsum = neg.query_sum(lb, rb);
            while(lb < rb) {
                int mid = (lb+rb) >> 1;
                int psum = pos.query_sum(stolb, mid);
                if(psum - nsum >= x.second) {
                    rb = mid;
                }
                else {
                    lb = mid+1;
                }
            }
            int psum = pos.query_sum(stolb, lb);
            if(psum - nsum >= x.second) {
                b[x.first].k = b[lb].c;
            }
        }
        
    }
    for(int i=1; i<=Q; i++) {
        if(b[i].t == 3) {
            cout << b[i].k << "\n";
        }
    }
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    for(int i=1; i<=t; i++) {
        solve(i);
    }
}

• 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