oj.uz

Submission #804447

# Submission time Handle Problem Language Result Execution time Memory
804447 2023-08-03T08:46:01 Z TheSahib Food Court (JOI21_foodcourt) C++14
13 / 100
 1000 ms 57540 KB 
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int oo = 1e9 + 9;
const int MAX = 3e5 + 5;

ll n, m, q;



ll tree[MAX * 5];
ll lazy[MAX * 5];

void relax(int node, int l, int r){
    if(!lazy[node]) return;
    tree[node] += lazy[node];
    if(l != r){
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(int node, int l, int r, int ql, int qr, int val){
    relax(node, l, r);
    if(ql > r || qr < l) return;
    if(ql <= l && r <= qr){
        lazy[node] += val;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2, l, mid, ql, qr, val);
    update(node * 2 + 1, mid + 1, r, ql, qr, val);
    tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}

ll ask(int node, int l, int r, int ql, int qr){
    if(ql > r || qr < l) return 1e18;
    relax(node, l, r);
    if(ql <= l && r <= qr){
        return tree[node];
    }
    int mid = (l + r) / 2;
    return min(ask(node * 2, l, mid, ql, qr), ask(node * 2 + 1, mid + 1, r, ql, qr));
}

vector<array<ll, 4>> events[MAX];
vector<array<ll, 2>> quer[MAX];

int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++)
    {
        int t; cin >> t;
        if(t == 1){
            ll l, r, c, k; cin >> l >> r >> c >> k;
            events[l].push_back({t, i, c, k});
            events[r + 1].push_back({-t, i, c, k});
        }
        else if(t == 2){
            ll l, r, k; cin >> l >> r >> k;
            events[l].push_back({t, i, 0, -k});
            events[r + 1].push_back({-t, i, 0, -k});
        }
        else{
            ll a, b; cin >> a >> b;
            quer[a].push_back({i, b});
        }
    }
    vector<int> ans(q + 1, -1);
    set<pii> st;
    for (int i = 1; i <= n; i++)
    {
        for(auto& e:events[i]){
            if(e[0] > 0){
                update(1, 0, MAX, e[1], MAX, e[3]);
                if(e[0] == 1){
                    st.insert({e[1], e[2]});
                }
            }
            else{
                update(1, 0, MAX, e[1], MAX, -e[3]);
                if(e[0] == -1){
                    st.erase({e[1], e[2]});
                }
            }
        }
        for(auto& e:quer[i]){
            int idx = e[0];
            ll b = e[1];
            ll mn = ask(1, 0, MAX, 0, idx);
            ll a = ask(1, 0, MAX, idx, idx);
            if(a - mn < b){
                ans[idx] = 0;
                continue;
            }
            int l = 0, r = idx - 1;
            int c = 0;
            while(l <= r){
                int mid = (l + r) / 2;
                if(ask(1, 0, MAX, mid, idx) - mn < b){
                    l = mid + 1;
                    c = mid;
                }
                else{
                    r = mid - 1;
                }
            }
            auto itr = st.upper_bound({c, oo});
            ans[idx] = itr->second;
        }
    }
    for (int i = 0; i <= q; i++)
    {
        if(ans[i] < 0) continue;
        cout << ans[i] << '\n';
    }
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 23868 KB Output is correct
2 Correct 112 ms 24272 KB Output is correct
3 Correct 105 ms 23884 KB Output is correct
4 Correct 102 ms 23872 KB Output is correct
5 Correct 118 ms 24208 KB Output is correct
6 Correct 112 ms 24200 KB Output is correct
7 Correct 84 ms 22544 KB Output is correct
8 Correct 94 ms 22808 KB Output is correct
9 Correct 113 ms 24240 KB Output is correct
10 Correct 117 ms 24256 KB Output is correct
11 Correct 110 ms 24204 KB Output is correct
12 Correct 103 ms 24192 KB Output is correct
13 Incorrect 121 ms 22852 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 50684 KB Output is correct
2 Correct 604 ms 43324 KB Output is correct
3 Correct 979 ms 53972 KB Output is correct
4 Correct 598 ms 45520 KB Output is correct
5 Correct 614 ms 46244 KB Output is correct
6 Correct 915 ms 57540 KB Output is correct
7 Correct 567 ms 49108 KB Output is correct
8 Correct 618 ms 48400 KB Output is correct
9 Execution timed out 1080 ms 53580 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 23488 KB Output is correct
2 Correct 228 ms 24444 KB Output is correct
3 Correct 240 ms 24572 KB Output is correct
4 Correct 196 ms 21740 KB Output is correct
5 Correct 218 ms 23460 KB Output is correct
6 Correct 246 ms 24804 KB Output is correct
7 Correct 171 ms 22796 KB Output is correct
8 Correct 171 ms 21964 KB Output is correct
9 Correct 209 ms 24452 KB Output is correct
10 Correct 154 ms 22156 KB Output is correct
11 Correct 248 ms 25164 KB Output is correct
12 Correct 221 ms 25188 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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