oj.uz

Submission #797301

# Submission time Handle Problem Language Result Execution time Memory
797301 2023-07-29T08:59:50 Z vjudge1 Food Court (JOI21_foodcourt) C++17
7 / 100
 448 ms 524288 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 70000;
const int B = 266;

int n, m, q;

deque<pair<int, ll>> g[N]; 
struct obj {
    ll pos, c, k;
};

deque<obj> que[N + 10], bl_q[N / B + 10];

void add(deque<obj> &q, int c, ll k) {
    if(q.empty()) q.push_back({0, c, k});
    else q.push_back({(q.back().pos + q.back().k), c, k});
}

ll find(deque<obj> &q, ll b) {
    if(q.empty() || q.back().pos + q.back().k <= b || b < 0) return 0;
    int l = 0, r = (int)q.size();
    while(r - l > 1) {
        int mid = (l + r) / 2;
        if(b < q[mid].pos) r = mid;
        else l = mid;
    }
    return q[l].c;
}
void push(int bl) {
    if(bl_q[bl].empty()) return;
    for(int i = bl * B; i < (bl + 1) * B; i++) {
        for(obj z : bl_q[bl]) 
            add(que[i], z.c, z.k);
    }
    bl_q[bl].clear();
}

ll answer(int a, ll b) {
    b--;
    ll ans = find(que[a], b);
    if(ans) return ans;
    if(!que[a].empty()) b -= que[a].back().pos + que[a].back().k;
    return find(bl_q[a / B], b);
}

vector<vector<ll>> qr;
void solve() {
    for(auto g : qr) {
        if(g[0] == 1) {
            ll l, r, c, k;
            l = g[1], r = g[2], c = g[3], k = g[4];
            while(l <= r) {
                bool flag = (l % B == 0 && l + B - 1 <= r);
                if(flag) add(bl_q[l / B], c, k), l += B;
                else {
                    push(l / B);
                    add(que[l], c, k);
                    l++;
                }
            }
        }
        if(g[0] == 3) {
            ll a, b;
            a = g[1], b = g[2];
            cout << answer(a, b) << '\n';
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    if(n <= 2000 && q <= 2000) {
        for(int i = 0; i < q; i++) {
            int t;
            cin >> t;
            if(t == 1) {
                ll l, r, c, k;
                cin >> l >> r >> c >> k;
                for(int j = l; j <= r; j++) {
                    g[j].push_back({c, k});
                }
            }
            if(t == 2) {
                ll l, r, k;
                cin >> l >> r >> k;
                for(int j = l; j <= r; j++) {
                    int p = k;
                    while(!g[j].empty() && g[j].front().second <= p) {
                        p -= g[j].front().second;
                        g[j].pop_front();
                    }
                    if(!g[j].empty()) 
                        g[j][0].second -= p;
                }
            }
            if(t == 3) {
                ll a, b;
                cin >> a >> b;
                int ans = 0;
                for(auto [c, k] : g[a]) {
                    if(b > k) b -= k;
                    else {ans = c; break;}
                }
                cout << ans << '\n';    
                  
            }
        }
        return 0;
    }
    bool flag = 1;
    for(int i = 0; i < q; i++) {
        int t;
        cin >> t;
        ll l, r, c, k, a, b;
        if(t == 1) {
            cin >> l >> r >> c >> k;
            qr.push_back({t, l, r, c, k});
        }
        if(t == 2) {
            cin >> l >> r >> k;
            flag = 0;
            qr.push_back({t, l, r, k});
        }
        if(t == 3) {
            cin >> a >> b;
            qr.push_back({t, a, b});
        }
    } 
    if(flag) {
        solve();
    }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 93972 KB Output is correct
2 Correct 64 ms 94360 KB Output is correct
3 Correct 64 ms 101020 KB Output is correct
4 Correct 70 ms 104624 KB Output is correct
5 Correct 56 ms 93640 KB Output is correct
6 Correct 50 ms 93520 KB Output is correct
7 Correct 70 ms 106112 KB Output is correct
8 Correct 66 ms 101792 KB Output is correct
9 Correct 65 ms 94460 KB Output is correct
10 Correct 80 ms 101264 KB Output is correct
11 Correct 66 ms 98308 KB Output is correct
12 Correct 74 ms 94684 KB Output is correct
13 Correct 64 ms 94568 KB Output is correct
14 Correct 71 ms 95724 KB Output is correct
15 Correct 63 ms 96592 KB Output is correct
16 Correct 66 ms 95688 KB Output is correct
17 Correct 59 ms 93940 KB Output is correct
18 Correct 62 ms 94144 KB Output is correct
19 Correct 50 ms 93652 KB Output is correct
20 Correct 52 ms 93560 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 93972 KB Output is correct
2 Correct 64 ms 94360 KB Output is correct
3 Correct 64 ms 101020 KB Output is correct
4 Correct 70 ms 104624 KB Output is correct
5 Correct 56 ms 93640 KB Output is correct
6 Correct 50 ms 93520 KB Output is correct
7 Correct 70 ms 106112 KB Output is correct
8 Correct 66 ms 101792 KB Output is correct
9 Correct 65 ms 94460 KB Output is correct
10 Correct 80 ms 101264 KB Output is correct
11 Correct 66 ms 98308 KB Output is correct
12 Correct 74 ms 94684 KB Output is correct
13 Correct 64 ms 94568 KB Output is correct
14 Correct 71 ms 95724 KB Output is correct
15 Correct 63 ms 96592 KB Output is correct
16 Correct 66 ms 95688 KB Output is correct
17 Correct 59 ms 93940 KB Output is correct
18 Correct 62 ms 94144 KB Output is correct
19 Correct 50 ms 93652 KB Output is correct
20 Correct 52 ms 93560 KB Output is correct
21 Correct 60 ms 94280 KB Output is correct
22 Correct 63 ms 94476 KB Output is correct
23 Correct 71 ms 100996 KB Output is correct
24 Correct 71 ms 104632 KB Output is correct
25 Correct 50 ms 93576 KB Output is correct
26 Correct 50 ms 93560 KB Output is correct
27 Correct 70 ms 105468 KB Output is correct
28 Correct 68 ms 102476 KB Output is correct
29 Correct 68 ms 96164 KB Output is correct
30 Correct 68 ms 100812 KB Output is correct
31 Correct 66 ms 98272 KB Output is correct
32 Correct 66 ms 94416 KB Output is correct
33 Correct 57 ms 94504 KB Output is correct
34 Correct 69 ms 96724 KB Output is correct
35 Correct 66 ms 95216 KB Output is correct
36 Correct 65 ms 95564 KB Output is correct
37 Correct 49 ms 93640 KB Output is correct
38 Correct 50 ms 93644 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 93972 KB Output is correct
2 Correct 64 ms 94360 KB Output is correct
3 Correct 64 ms 101020 KB Output is correct
4 Correct 70 ms 104624 KB Output is correct
5 Correct 56 ms 93640 KB Output is correct
6 Correct 50 ms 93520 KB Output is correct
7 Correct 70 ms 106112 KB Output is correct
8 Correct 66 ms 101792 KB Output is correct
9 Correct 65 ms 94460 KB Output is correct
10 Correct 80 ms 101264 KB Output is correct
11 Correct 66 ms 98308 KB Output is correct
12 Correct 74 ms 94684 KB Output is correct
13 Correct 64 ms 94568 KB Output is correct
14 Correct 71 ms 95724 KB Output is correct
15 Correct 63 ms 96592 KB Output is correct
16 Correct 66 ms 95688 KB Output is correct
17 Correct 59 ms 93940 KB Output is correct
18 Correct 62 ms 94144 KB Output is correct
19 Correct 50 ms 93652 KB Output is correct
20 Correct 52 ms 93560 KB Output is correct
21 Incorrect 76 ms 97912 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 93972 KB Output is correct
2 Correct 64 ms 94360 KB Output is correct
3 Correct 64 ms 101020 KB Output is correct
4 Correct 70 ms 104624 KB Output is correct
5 Correct 56 ms 93640 KB Output is correct
6 Correct 50 ms 93520 KB Output is correct
7 Correct 70 ms 106112 KB Output is correct
8 Correct 66 ms 101792 KB Output is correct
9 Correct 65 ms 94460 KB Output is correct
10 Correct 80 ms 101264 KB Output is correct
11 Correct 66 ms 98308 KB Output is correct
12 Correct 74 ms 94684 KB Output is correct
13 Correct 64 ms 94568 KB Output is correct
14 Correct 71 ms 95724 KB Output is correct
15 Correct 63 ms 96592 KB Output is correct
16 Correct 66 ms 95688 KB Output is correct
17 Correct 59 ms 93940 KB Output is correct
18 Correct 62 ms 94144 KB Output is correct
19 Correct 50 ms 93652 KB Output is correct
20 Correct 52 ms 93560 KB Output is correct
21 Correct 60 ms 94280 KB Output is correct
22 Correct 63 ms 94476 KB Output is correct
23 Correct 71 ms 100996 KB Output is correct
24 Correct 71 ms 104632 KB Output is correct
25 Correct 50 ms 93576 KB Output is correct
26 Correct 50 ms 93560 KB Output is correct
27 Correct 70 ms 105468 KB Output is correct
28 Correct 68 ms 102476 KB Output is correct
29 Correct 68 ms 96164 KB Output is correct
30 Correct 68 ms 100812 KB Output is correct
31 Correct 66 ms 98272 KB Output is correct
32 Correct 66 ms 94416 KB Output is correct
33 Correct 57 ms 94504 KB Output is correct
34 Correct 69 ms 96724 KB Output is correct
35 Correct 66 ms 95216 KB Output is correct
36 Correct 65 ms 95564 KB Output is correct
37 Correct 49 ms 93640 KB Output is correct
38 Correct 50 ms 93644 KB Output is correct
39 Incorrect 76 ms 97912 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 93972 KB Output is correct
2 Correct 64 ms 94360 KB Output is correct
3 Correct 64 ms 101020 KB Output is correct
4 Correct 70 ms 104624 KB Output is correct
5 Correct 56 ms 93640 KB Output is correct
6 Correct 50 ms 93520 KB Output is correct
7 Correct 70 ms 106112 KB Output is correct
8 Correct 66 ms 101792 KB Output is correct
9 Correct 65 ms 94460 KB Output is correct
10 Correct 80 ms 101264 KB Output is correct
11 Correct 66 ms 98308 KB Output is correct
12 Correct 74 ms 94684 KB Output is correct
13 Correct 64 ms 94568 KB Output is correct
14 Correct 71 ms 95724 KB Output is correct
15 Correct 63 ms 96592 KB Output is correct
16 Correct 66 ms 95688 KB Output is correct
17 Correct 59 ms 93940 KB Output is correct
18 Correct 62 ms 94144 KB Output is correct
19 Correct 50 ms 93652 KB Output is correct
20 Correct 52 ms 93560 KB Output is correct
21 Correct 60 ms 94280 KB Output is correct
22 Correct 63 ms 94476 KB Output is correct
23 Correct 71 ms 100996 KB Output is correct
24 Correct 71 ms 104632 KB Output is correct
25 Correct 50 ms 93576 KB Output is correct
26 Correct 50 ms 93560 KB Output is correct
27 Correct 70 ms 105468 KB Output is correct
28 Correct 68 ms 102476 KB Output is correct
29 Correct 68 ms 96164 KB Output is correct
30 Correct 68 ms 100812 KB Output is correct
31 Correct 66 ms 98272 KB Output is correct
32 Correct 66 ms 94416 KB Output is correct
33 Correct 57 ms 94504 KB Output is correct
34 Correct 69 ms 96724 KB Output is correct
35 Correct 66 ms 95216 KB Output is correct
36 Correct 65 ms 95564 KB Output is correct
37 Correct 49 ms 93640 KB Output is correct
38 Correct 50 ms 93644 KB Output is correct
39 Incorrect 76 ms 97912 KB Output isn't correct
40 Halted 0 ms 0 KB -