oj.uz

Submission #813443

# Submission time Handle Problem Language Result Execution time Memory
813443 2023-08-07T17:59:30 Z ParsaS Food Court (JOI21_foodcourt) C++17
2 / 100
 61 ms 32996 KB 
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 25e4 + 5;
int n, m, q;
int C[N];
vector<int> vadd[N], vrem[N], vec;
vector<pair<int, int > > qr[N];
int ans[N];
int S[N << 2];

struct node {
    int rem, cnt, ex;
    node() {
        rem = cnt = ex = 0;
    }
    void clear() {
        cnt = rem = ex = 0;
    }
} seg[N << 2];

void shift(int v, int tl, int tr) {
    if (tl == tr)
        return;
    int lc = v << 1, rc = v << 1 | 1;
    seg[lc].ex += max(0, seg[v].ex - seg[lc].cnt);
    seg[lc].rem += seg[v].rem + min(seg[v].ex, seg[lc].cnt);
    seg[lc].cnt = seg[v].cnt + max(0, seg[lc].cnt - seg[v].ex);
    seg[rc].ex += max(0, seg[v].ex - seg[rc].cnt);
    seg[rc].rem += seg[v].rem + min(seg[v].ex, seg[rc].cnt);
    seg[rc].cnt = seg[v].cnt + max(0, seg[rc].cnt - seg[v].ex);

    seg[v].clear();
}

void ADD(int l, int r, int c, int v = 1, int tl = 1, int tr = n) {
    shift(v, tl, tr);
    if (l > tr || r < tl)
        return;
    if (tl >= l && tr <= r) {
        seg[v].cnt += c;
        return;
    }
    int mid = (tl + tr) >> 1;
    ADD(l, r, c, v << 1, tl, mid);
    ADD(l, r, c, v << 1 | 1, mid + 1, tr);
}
void REM(int l, int r, int c, int v = 1, int tl = 1, int tr = n) {
    shift(v, tl, tr);
    if (l > tr || r < tl) {
        return;
    }
    if (tl >= l && tr <= r) {
        if (tl == tr) {
            int k = min(seg[v].cnt, c);
            seg[v].cnt -= k;
            seg[v].rem += k;
            seg[v].ex += c - k;
        }
        else
            seg[v].ex += c;
        return;
    }
    int mid = (tl + tr) >> 1;
    REM(l, r, c, v << 1, tl, mid);
    REM(l, r, c, v << 1 | 1, mid + 1, tr);
}
node query(int i, int v = 1, int tl = 1, int tr = n) {
    shift(v, tl, tr);
    if (tl == tr) {
        return seg[v];
    }
    int mid = (tl + tr) >> 1;
    if (i <= mid)
        return query(i, v << 1, tl, mid);
    return query(i, v << 1 | 1, mid + 1, tr);
}

void upd(int i, int val, int v = 1, int tl = 0, int tr = (int)vec.size()) {
    if (tl == tr) {
        S[v] += val;
        return;
    }
    int mid = (tl + tr) >> 1;
    if (i <= mid)
        upd(i, val, v << 1, tl, mid);
    else
        upd(i, val, v << 1 | 1, mid + 1, tr);
    S[v] = S[v << 1] + S[v << 1 | 1];
}
int query2(int x, int v = 1, int tl = 0, int tr = (int)vec.size()) {
    if (tl == tr)
        return tl;
    int mid = (tl + tr) >> 1;
    if (S[v << 1] >= x)
        return query2(x, v << 1, tl, mid);
    return query2(x - S[v << 1], v << 1 | 1, mid + 1, tr);
}


void solve() {
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        ans[i] = -1;
        int t; cin >> t;
        if (t == 1) {
            int l, r, c, k; cin >> l >> r >> k >> c;
            C[(int)vec.size()] = c;
            vadd[l].pb((int)vec.size());
            vrem[r + 1].pb((int)vec.size());
            vec.pb(k);

            ADD(l, r, c);
        }
        else if (t == 2) {
            int l, r, c; cin >> l >> r >> c;
            REM(l, r, c);

        }
        else {
            int a, b; cin >> a >> b;
            node v = query(a);
            if (v.cnt < b) {
                ans[i] = 0;
            }
            else {
                qr[a].pb(mp(v.rem + b, i));
            }
        }
        continue;
        for (int j = 1; j <= n; j++) {
            node u = query(j);
            cout << u.cnt << ' ';
        }
        cout << endl;
        node u = query(1);
        cout << u.cnt << ' ' << u.rem << ' ' << u.ex << endl;
    }
    for (int i = 1; i <= n; i++) {
        for (auto x : vadd[i]) {
            upd(x, C[x]);
        }
        for (auto x : vrem[i]) {
            upd(x, -C[x]);
        }
        for (auto [c, j] : qr[i]) {
            ans[j] = vec[query2(c)];
        }
    }
    for (int i = 0; i < q; i++) {
        if (ans[i] != -1)
            cout << ans[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29780 KB Output is correct
2 Correct 16 ms 29708 KB Output is correct
3 Correct 19 ms 29664 KB Output is correct
4 Correct 16 ms 29752 KB Output is correct
5 Correct 14 ms 29760 KB Output is correct
6 Correct 14 ms 29704 KB Output is correct
7 Correct 16 ms 29744 KB Output is correct
8 Correct 15 ms 29708 KB Output is correct
9 Correct 16 ms 29780 KB Output is correct
10 Correct 14 ms 29704 KB Output is correct
11 Correct 14 ms 29792 KB Output is correct
12 Correct 14 ms 29684 KB Output is correct
13 Correct 13 ms 29652 KB Output is correct
14 Correct 14 ms 29780 KB Output is correct
15 Correct 14 ms 29640 KB Output is correct
16 Correct 14 ms 29780 KB Output is correct
17 Correct 15 ms 29692 KB Output is correct
18 Correct 14 ms 29776 KB Output is correct
19 Correct 15 ms 29780 KB Output is correct
20 Correct 17 ms 29780 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29780 KB Output is correct
2 Correct 16 ms 29708 KB Output is correct
3 Correct 19 ms 29664 KB Output is correct
4 Correct 16 ms 29752 KB Output is correct
5 Correct 14 ms 29760 KB Output is correct
6 Correct 14 ms 29704 KB Output is correct
7 Correct 16 ms 29744 KB Output is correct
8 Correct 15 ms 29708 KB Output is correct
9 Correct 16 ms 29780 KB Output is correct
10 Correct 14 ms 29704 KB Output is correct
11 Correct 14 ms 29792 KB Output is correct
12 Correct 14 ms 29684 KB Output is correct
13 Correct 13 ms 29652 KB Output is correct
14 Correct 14 ms 29780 KB Output is correct
15 Correct 14 ms 29640 KB Output is correct
16 Correct 14 ms 29780 KB Output is correct
17 Correct 15 ms 29692 KB Output is correct
18 Correct 14 ms 29776 KB Output is correct
19 Correct 15 ms 29780 KB Output is correct
20 Correct 17 ms 29780 KB Output is correct
21 Incorrect 13 ms 29712 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 32996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 31016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29780 KB Output is correct
2 Correct 16 ms 29708 KB Output is correct
3 Correct 19 ms 29664 KB Output is correct
4 Correct 16 ms 29752 KB Output is correct
5 Correct 14 ms 29760 KB Output is correct
6 Correct 14 ms 29704 KB Output is correct
7 Correct 16 ms 29744 KB Output is correct
8 Correct 15 ms 29708 KB Output is correct
9 Correct 16 ms 29780 KB Output is correct
10 Correct 14 ms 29704 KB Output is correct
11 Correct 14 ms 29792 KB Output is correct
12 Correct 14 ms 29684 KB Output is correct
13 Correct 13 ms 29652 KB Output is correct
14 Correct 14 ms 29780 KB Output is correct
15 Correct 14 ms 29640 KB Output is correct
16 Correct 14 ms 29780 KB Output is correct
17 Correct 15 ms 29692 KB Output is correct
18 Correct 14 ms 29776 KB Output is correct
19 Correct 15 ms 29780 KB Output is correct
20 Correct 17 ms 29780 KB Output is correct
21 Incorrect 61 ms 32996 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 30036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29780 KB Output is correct
2 Correct 16 ms 29708 KB Output is correct
3 Correct 19 ms 29664 KB Output is correct
4 Correct 16 ms 29752 KB Output is correct
5 Correct 14 ms 29760 KB Output is correct
6 Correct 14 ms 29704 KB Output is correct
7 Correct 16 ms 29744 KB Output is correct
8 Correct 15 ms 29708 KB Output is correct
9 Correct 16 ms 29780 KB Output is correct
10 Correct 14 ms 29704 KB Output is correct
11 Correct 14 ms 29792 KB Output is correct
12 Correct 14 ms 29684 KB Output is correct
13 Correct 13 ms 29652 KB Output is correct
14 Correct 14 ms 29780 KB Output is correct
15 Correct 14 ms 29640 KB Output is correct
16 Correct 14 ms 29780 KB Output is correct
17 Correct 15 ms 29692 KB Output is correct
18 Correct 14 ms 29776 KB Output is correct
19 Correct 15 ms 29780 KB Output is correct
20 Correct 17 ms 29780 KB Output is correct
21 Incorrect 13 ms 29712 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 29780 KB Output is correct
2 Correct 16 ms 29708 KB Output is correct
3 Correct 19 ms 29664 KB Output is correct
4 Correct 16 ms 29752 KB Output is correct
5 Correct 14 ms 29760 KB Output is correct
6 Correct 14 ms 29704 KB Output is correct
7 Correct 16 ms 29744 KB Output is correct
8 Correct 15 ms 29708 KB Output is correct
9 Correct 16 ms 29780 KB Output is correct
10 Correct 14 ms 29704 KB Output is correct
11 Correct 14 ms 29792 KB Output is correct
12 Correct 14 ms 29684 KB Output is correct
13 Correct 13 ms 29652 KB Output is correct
14 Correct 14 ms 29780 KB Output is correct
15 Correct 14 ms 29640 KB Output is correct
16 Correct 14 ms 29780 KB Output is correct
17 Correct 15 ms 29692 KB Output is correct
18 Correct 14 ms 29776 KB Output is correct
19 Correct 15 ms 29780 KB Output is correct
20 Correct 17 ms 29780 KB Output is correct
21 Incorrect 13 ms 29712 KB Output isn't correct
22 Halted 0 ms 0 KB -