Submission #1062931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062931		onbert	푸드 코트 (JOI21_foodcourt)	C++17	100 / 100	424 ms	54512 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
    int val, ti, t;
};
const int maxn = 250005, maxN = 1e6 + 5, INF = 1e18;
int n, m, q;
vector<thing> delta[maxn];
vector<pair<int,int>> qry[maxn];

int seg[maxN], lazy[maxN];
void push(int id) {
    if (id*2 < maxN) lazy[id*2] += lazy[id];
    if (id*2+1 < maxN) lazy[id*2+1] += lazy[id];
    seg[id] += lazy[id];
    lazy[id] = 0;
}
void update(int id, int l, int r, int findl, int findr, int val) {
    push(id);
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        lazy[id] += val;
        push(id);
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val);
    update(id*2+1, mid+1, r, findl, findr, val);
    seg[id] = min(seg[id*2], seg[id*2+1]);
}
int mn(int id, int l, int r, int findl, int findr) {
    push(id);
    if (r<findl || findr<l) return INF;
    if (findl<=l && r<=findr) return seg[id];
    int mid = (l+r)/2;
    return min(mn(id*2, l, mid, findl, findr), mn(id*2+1, mid+1, r, findl, findr));
}

int fen[maxn][2];
void update2(int id, int val, int j) {
    while (id<=q) {
        fen[id][j] += val;
        id += (id & -id);
    }
}
int sum(int id, int j) {
    int val = 0;
    while (id>=1) {
        val += fen[id][j];
        id -= (id & -id);
    }
    return val;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    int id[q+1], ans[q+1];
    for (int i=1;i<=q;i++) ans[i] = -2;
    for (int i=1;i<=q;i++) {
        int t;
        cin >> t;
        if (t==1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            delta[l].push_back({k, i, 0});
            delta[r+1].push_back({-k, i, 0});
            id[i] = c;
        } else if (t==2) {
            int l, r, k;
            cin >> l >> r >> k;
            delta[l].push_back({-k, i, 1});
            delta[r+1].push_back({k, i, 1});
        } else if (t==3) {
            int x, y;
            cin >> x >> y;
            qry[x].push_back({y, i});
        }
    }
    for (int i=1;i<=n;i++) {
        for (auto [val, ti, t]:delta[i]) {
            update2(ti, val, t);
            update(1, 1, q, ti, q, val);
        }
        for (auto [x, ti]:qry[i]) {
            x += -sum(ti, 1) + min(mn(1, 1, q, 1, ti), (int)0);
            // cout << i << " " << x << endl;
            if (sum(ti, 0) < x) {
                ans[ti] = 0;
                continue;
            }
            int l = 1, r = ti;
            while (l<r) {
                int mid = (l+r)/2;
                if (sum(mid, 0) >= x) r = mid;
                else l = mid+1;
            }
            ans[ti] = id[l];
        }
    }
    for (int i=1;i<=q;i++) if (ans[i]!=-2) cout << ans[i] << '\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