Submission #909868

#	Time	Username	Problem	Language	Result	Execution time	Memory
909868		Trisanu_Das	Food Court (JOI21_foodcourt)	C++17	35 / 100	357 ms	230152 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int INF = 1e9;
const int LOG = 18;

void add(int &a, int b) {
    a += b;
    if (a < 0) a += mod;
    if (a >= mod) a -= mod;
}

template <typename T>
void chkmin(T &a, T b) {
    if (a > b) a = b;
}

template <typename T>
void chkmax(T &a, T b) {
    if (a < b) a = b;
}

int _pow(int a, int n) {
    if (n == 0) return 1;
    int res = _pow(a, n / 2);
    if (n % 2) return (1ll * res * res % mod * a % mod);
    else return 1ll * res * res % mod;
}

int n, m, nq;

struct shape {
    int op, l, r, c, k;
    int pos;
    long long b;
} q[300009];

deque<pair<long long, long long>> deq[300009];

void sub1() {
    for (int run = 1; run <= nq; run++) {
        int op = q[run].op;
        if (op <= 2) {
            int l = q[run].l, r = q[run].r, c = q[run].c, k = q[run].k;
            if (op == 1) {
                for (int i = l; i <= r; i++) {
                    if (deq[i].empty() || deq[i].back().first != c) deq[i].push_back({c, k});
                    else deq[i].back().second += k;
                }
            } else {
                for (int i = l; i <= r; i++) {
                    int remain = k;
                    while (deq[i].size()) {
                        if (deq[i].front().second <= remain) remain -= deq[i].front().second, deq[i].pop_front();
                        else {
                            deq[i].front().second -= remain;
                            break;
                        }
                    }
                }
            }
        } else {
            int pos = q[run].pos;
            long long b = q[run].b;
            deque<pair<long long, long long>> New = deq[pos];
            long long sum = 0;
            int res = 0;
            while (!New.empty()) {
                if (sum + New.front().second >= b) {
                    res = New.front().first;
                    break;
                }
                sum += New.front().second;
                New.pop_front();
            }
            cout << res << "\n";
        }
    }
}

bool check_sub2() {
    if (max(n, nq) > 65000) return false;
    for (int i = 1; i <= nq; i++) {
        if (q[i].op == 1) {
            if (q[i].r - q[i].l > 10) return false;
            if (q[i].k != 1) return false;
        }
    }
    return true;
}

const int N = 2.5 * 1e5;
long long T[300009 * 4], lazy[300009 * 4];

void down_leave_sub2(int id) {
    long long &t = lazy[id];
    T[id * 2] += t, T[id * 2 + 1] += t;
    lazy[id * 2] += t, lazy[id * 2 + 1] += t;
    t = 0;
}

void update_leave_sub2(int id, int l, int r, int u, int v, int k) {
    if (l > v || r < u) return;
    if (u <= l && r <= v) {
        T[id] += k;
        lazy[id] += k;
        if (k == -1) T[id] = lazy[id] = 0;
        return;
    }
    int mid = (l + r) / 2;
    down_leave_sub2(id);
    update_leave_sub2(id * 2, l, mid, u, v, k);
    update_leave_sub2(id * 2 + 1, mid + 1, r, u, v, k);
}

long long get_leave_sub2(int id, int l, int r, int pos) {
    if (l > pos || r < pos) return 0;
    if (l == r) return T[id];
    down_leave_sub2(id);
    int mid = (l + r) / 2;
    return get_leave_sub2(id * 2, l, mid, pos) + get_leave_sub2(id * 2 + 1, mid + 1, r, pos);
}

void leave_sub2(int pos) {
    long long leave = get_leave_sub2(1, 1, N, pos);
    update_leave_sub2(1, 1, N, pos, pos, -1);
    while (deq[pos].size()) {
        if (deq[pos].front().second <= leave) leave -= deq[pos].front().second, deq[pos].pop_front();
        else {
            deq[pos].front().second -= leave;
            break;
        }
    }
}

void sub2() {
    for (int run = 1; run <= nq; run++) {
        if (q[run].op <= 2) {
            int l = q[run].l, r = q[run].r, c = q[run].c, k = q[run].k;
            if (q[run].op == 1) {
                for (int i = l; i <= r; i++) {
                    leave_sub2(i);
                    if (deq[i].empty() || deq[i].back().first != c) deq[i].push_back({c, k});
                    else deq[i].back().second += k;
                }
            } else {
                int l = q[run].l, r = q[run].r, k = q[run].k;
                update_leave_sub2(1, 1, N, l, r, k);
            }
        } else {
            int pos = q[run].pos;
            long long b = q[run].b;
            leave_sub2(pos);
            deque<pair<long long, long long>> New = deq[pos];
            long long sum = 0;
            int res = 0;
            while (!New.empty()) {
                if (sum + New.front().second >= b) {
                    res = New.front().first;
                    break;
                }
                sum += New.front().second;
                New.pop_front();
            }
            cout << res << "\n";
        }
    }
}

struct info {
    long long sum, minn;
    friend info operator+(info x, info y) {
        info res;
        res.minn = min(x.minn, x.sum + y.minn);
        res.sum = x.sum + y.sum;
        return res;
    }
} laz[300009 * 4];

void down_leave_sub3(int id) {
    laz[id * 2] = laz[id * 2] + laz[id];
    laz[id * 2 + 1] = laz[id * 2 + 1] + laz[id];
    laz[id] = {0, 0};
}

void update_leave_sub3(int id, int l, int r, int u, int v, int k) {
    if (l > v || r < u) return;
    if (u <= l && r <= v) {
        info dat = {k, min(k, 0)};
        laz[id] = laz[id] + dat;
        return;
    }
    int mid = (l + r) / 2;
    down_leave_sub3(id);
    update_leave_sub3(id * 2, l, mid, u, v, k);
    update_leave_sub3(id * 2 + 1, mid + 1, r, u, v, k);
    T[id] = min(T[id * 2], T[id * 2 + 1]);
}

long long get_leave_sub3(int id, int l, int r, int pos) {
    if (l > pos || r < pos) return 0;
    if (l == r) return laz[id].sum - laz[id].minn;
    int mid = (l + r) / 2;
    down_leave_sub3(id);
    return get_leave_sub3(id * 2, l, mid, pos) + get_leave_sub3(id * 2 + 1, mid + 1, r, pos);
}

void sub3() {
    for (int run = 1; run <= nq; run++) {
        int l = q[run].l, r = q[run].r, k = q[run].k;
        if (q[run].op == 1) update_leave_sub3(1, 1, N, l, r, k);
        else if (q[run].op == 2) update_leave_sub3(1, 1, N, l, r, -k);
        else {
            int pos = q[run].pos;
            long long b = q[run].b;
            if (get_leave_sub3(1, 1, N, pos) >= b) cout << 1 << "\n";
            else cout << 0 << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> nq;
    for (int i = 1; i <= nq; i++) {
        cin >> q[i].op;
        if (q[i].op == 1) cin >> q[i].l >> q[i].r >> q[i].c >> q[i].k;
        else if (q[i].op == 2) cin >> q[i].l >> q[i].r >> q[i].k;
        else cin >> q[i].pos >> q[i].b;
    }
    if (n <= 2e3 && nq <= 2e3) sub1();
    else if (check_sub2()) sub2();
    else if (m == 1) sub3();
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11