oj.uz

Submission #1065512

# Submission time Handle Problem Language Result Execution time Memory
1065512 2024-08-19T08:48:19 Z 정민찬(#11118) Food Court (JOI21_foodcourt) C++17
68 / 100
 89 ms 51996 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

struct SegmentTree{
    vector<ll> tree;
    vector<ll> T;
    void init(ll n) {
        ll sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, 0);
        T.assign(n+1, 0);
    }
    void update(ll node, ll s, ll e, ll tar, ll val) {
        if (s > tar || tar > e) return;
        tree[node] += val;
        if (s == e) {
            return;
        }
        ll mid = s + e >> 1;
        update(node*2, s, mid, tar, val);
        update(node*2+1, mid+1, e, tar, val);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    ll query(ll node, ll s, ll e, ll l, ll r) {
        if (l > e || s > r) return 0;
        if (l <= s && e <= r) return tree[node];
        ll mid = s + e >> 1;
        return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
    }
    pll findLeft(ll node, ll s, ll e, ll l, ll r, ll k) {
        if (l > e || s > r) return {-1, 0};
        if (l <= s && e <= r && tree[node] < k) return {-1, tree[node]};
        if (s == e) return {s, 0};
        ll mid = s + e >> 1;
        pll t = findLeft(node*2, s, mid, l, r, k);
        if (t.first == -1) {
            pll t2 = findLeft(node*2+1, mid+1, e, l, r, k - t.second);
            return {t2.first, t.second + t2.second};
        }
        return t;
    }
};

struct Node{
    ll sum, mnl, mnidx;
};

Node Merge(Node u, Node v) {
    Node ret;
    ret.sum = u.sum + v.sum;
    if (u.mnl <= u.sum + v.mnl) {
        ret.mnl = u.mnl;
        ret.mnidx = u.mnidx;
    }
    else {
        ret.mnl = u.sum + v.mnl;
        ret.mnidx = v.mnidx;
    }
    return ret;
}

struct SegmentTree2{
    vector<Node> tree;
    void init(ll n) {
        ll sz = 1 << __lg(n-1) + 2;
        tree.resize(sz);
        build(1, 1, n);
    }
    void build(ll node, ll s, ll e) {
        if (s == e) {
            tree[node] = {0, 0, s-1};
            return;
        }
        ll mid = s + e >> 1;
        build(node*2, s, mid);
        build(node*2+1, mid+1, e);
        tree[node] = Merge(tree[node*2], tree[node*2+1]);
    }
    void update(ll node, ll s, ll e, ll tar, ll val) {
        if (s > tar || tar > e) return;
        if (s == e) {
            if (val < 0) tree[node] = {val, val, s};
            else tree[node] = {val, 0, s-1};
            return;
        }
        ll mid = s + e >> 1;
        update(node*2, s, mid, tar, val);
        update(node*2+1, mid+1, e, tar, val);
        tree[node] = Merge(tree[node*2], tree[node*2+1]);
    }
    Node query(ll node, ll s, ll e, ll l, ll r) {
        if (l <= s && e <= r) return tree[node];
        ll mid = s + e >> 1;
        if (r <= mid) return query(node*2, s, mid, l, r);
        if (l >= mid+1) return query(node*2+1, mid+1, e, l, r);
        return Merge(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
    }
};

vector<array<ll,3>> upd[250010];
vector<pll> qry[250010];

SegmentTree pseg, mseg;
SegmentTree2 seg2;

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    ll N, M, Q;
    cin >> N >> M >> Q;
    vector<ll> num(Q + 1, -1);
    for (ll i=1; i<=Q; i++) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll l, r, c, k;
            cin >> l >> r >> c >> k;
            upd[l].push_back({i, k, c});
            upd[r+1].push_back({i, -k, c});
            num[i] = c;
        }
        else if (t == 2) {
            ll l, r, k;
            cin >> l >> r >> k;
            upd[l].push_back({i, k, 0});
            upd[r+1].push_back({i, -k, 0});
        }
        else {
            ll a, b;
            cin >> a >> b;
            qry[a].push_back({i, b});
        }
    }
    pseg.init(Q);
    mseg.init(Q);
    seg2.init(Q);
    vector<ll> ans(Q+1, -1);
    for (ll i=1; i<=M; i++) {
        for (auto &[j, k, c] : upd[i]) {
            if (c != 0) {
                pseg.update(1, 1, Q, j, k);
                if (k < 0) seg2.update(1, 1, Q, j, 0);
                else seg2.update(1, 1, Q, j, k);
            }
            else {
                mseg.update(1, 1, Q, j, k);
                if (k < 0) seg2.update(1, 1, Q, j, 0);
                else seg2.update(1, 1, Q, j, -k);
            }
        }
        for (auto &[j, cnt] : qry[i]) {
            Node ret = seg2.query(1, 1, Q, 1, j);
            ll mret = mseg.query(1, 1, Q, ret.mnidx + 1, j);
            if (pseg.query(1, 1, Q, ret.mnidx+1, j) < mret + cnt) {
                ans[j] = 0;
                continue;
            }
            ll pret = pseg.findLeft(1, 1, Q, ret.mnidx+1, j, mret + cnt).first;
            assert(pret != -1);
            ans[j] = num[pret];
        }
    }
    for (ll i=1; i<=Q; i++) {
        if (ans[i] != -1) {
            cout << ans[i] << '\n';
        }
    }
}

Compilation message

foodcourt.cpp: In member function 'void SegmentTree::init(ll)':
foodcourt.cpp:12:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   12 |         ll sz = 1 << __lg(n-1) + 2;
      |                      ~~~~~~~~~~^~~
foodcourt.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll)':
foodcourt.cpp:22:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         ll mid = s + e >> 1;
      |                  ~~^~~
foodcourt.cpp: In member function 'll SegmentTree::query(ll, ll, ll, ll, ll)':
foodcourt.cpp:30:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         ll mid = s + e >> 1;
      |                  ~~^~~
foodcourt.cpp: In member function 'pll SegmentTree::findLeft(ll, ll, ll, ll, ll, ll)':
foodcourt.cpp:37:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         ll mid = s + e >> 1;
      |                  ~~^~~
foodcourt.cpp: In member function 'void SegmentTree2::init(ll)':
foodcourt.cpp:68:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   68 |         ll sz = 1 << __lg(n-1) + 2;
      |                      ~~~~~~~~~~^~~
foodcourt.cpp: In member function 'void SegmentTree2::build(ll, ll, ll)':
foodcourt.cpp:77:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         ll mid = s + e >> 1;
      |                  ~~^~~
foodcourt.cpp: In member function 'void SegmentTree2::update(ll, ll, ll, ll, ll)':
foodcourt.cpp:89:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         ll mid = s + e >> 1;
      |                  ~~^~~
foodcourt.cpp: In member function 'Node SegmentTree2::query(ll, ll, ll, ll, ll)':
foodcourt.cpp:96:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         ll mid = s + e >> 1;
      |                  ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 5 ms 12376 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 4 ms 12472 KB Output is correct
6 Correct 4 ms 12520 KB Output is correct
7 Correct 5 ms 12380 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 5 ms 12376 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 4 ms 12472 KB Output is correct
6 Correct 4 ms 12520 KB Output is correct
7 Correct 5 ms 12380 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 4 ms 12276 KB Output is correct
22 Correct 4 ms 12380 KB Output is correct
23 Correct 4 ms 12380 KB Output is correct
24 Correct 4 ms 12380 KB Output is correct
25 Correct 5 ms 12380 KB Output is correct
26 Correct 4 ms 12380 KB Output is correct
27 Correct 5 ms 12380 KB Output is correct
28 Correct 5 ms 12380 KB Output is correct
29 Correct 4 ms 12380 KB Output is correct
30 Correct 5 ms 12380 KB Output is correct
31 Correct 4 ms 12532 KB Output is correct
32 Correct 4 ms 12380 KB Output is correct
33 Correct 4 ms 12380 KB Output is correct
34 Correct 4 ms 12384 KB Output is correct
35 Correct 4 ms 12380 KB Output is correct
36 Correct 4 ms 12380 KB Output is correct
37 Correct 4 ms 12380 KB Output is correct
38 Correct 4 ms 12452 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 22780 KB Output is correct
2 Correct 60 ms 22872 KB Output is correct
3 Correct 70 ms 22816 KB Output is correct
4 Correct 58 ms 22620 KB Output is correct
5 Correct 58 ms 22868 KB Output is correct
6 Correct 64 ms 22876 KB Output is correct
7 Correct 38 ms 21476 KB Output is correct
8 Correct 35 ms 21868 KB Output is correct
9 Correct 60 ms 22872 KB Output is correct
10 Correct 57 ms 23028 KB Output is correct
11 Correct 59 ms 23048 KB Output is correct
12 Correct 61 ms 22840 KB Output is correct
13 Correct 63 ms 22356 KB Output is correct
14 Correct 56 ms 22864 KB Output is correct
15 Correct 68 ms 23120 KB Output is correct
16 Correct 61 ms 23120 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 5 ms 12376 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 4 ms 12472 KB Output is correct
6 Correct 4 ms 12520 KB Output is correct
7 Correct 5 ms 12380 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 55 ms 22780 KB Output is correct
22 Correct 60 ms 22872 KB Output is correct
23 Correct 70 ms 22816 KB Output is correct
24 Correct 58 ms 22620 KB Output is correct
25 Correct 58 ms 22868 KB Output is correct
26 Correct 64 ms 22876 KB Output is correct
27 Correct 38 ms 21476 KB Output is correct
28 Correct 35 ms 21868 KB Output is correct
29 Correct 60 ms 22872 KB Output is correct
30 Correct 57 ms 23028 KB Output is correct
31 Correct 59 ms 23048 KB Output is correct
32 Correct 61 ms 22840 KB Output is correct
33 Correct 63 ms 22356 KB Output is correct
34 Correct 56 ms 22864 KB Output is correct
35 Correct 68 ms 23120 KB Output is correct
36 Correct 61 ms 23120 KB Output is correct
37 Correct 75 ms 22100 KB Output is correct
38 Correct 50 ms 21852 KB Output is correct
39 Correct 33 ms 21340 KB Output is correct
40 Correct 42 ms 21472 KB Output is correct
41 Correct 60 ms 22876 KB Output is correct
42 Correct 65 ms 23124 KB Output is correct
43 Correct 69 ms 23072 KB Output is correct
44 Correct 64 ms 23044 KB Output is correct
45 Correct 65 ms 22876 KB Output is correct
46 Correct 63 ms 22872 KB Output is correct
47 Correct 60 ms 22064 KB Output is correct
48 Correct 59 ms 23632 KB Output is correct
49 Correct 43 ms 21336 KB Output is correct
50 Correct 55 ms 22104 KB Output is correct
51 Correct 66 ms 23128 KB Output is correct
52 Correct 63 ms 23128 KB Output is correct
53 Correct 45 ms 22000 KB Output is correct
54 Correct 69 ms 23124 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 21760 KB Output is correct
2 Correct 62 ms 22324 KB Output is correct
3 Correct 65 ms 23888 KB Output is correct
4 Correct 43 ms 22100 KB Output is correct
5 Correct 54 ms 23152 KB Output is correct
6 Correct 61 ms 23928 KB Output is correct
7 Correct 43 ms 22316 KB Output is correct
8 Correct 35 ms 22028 KB Output is correct
9 Correct 48 ms 23368 KB Output is correct
10 Correct 39 ms 22608 KB Output is correct
11 Correct 55 ms 23920 KB Output is correct
12 Correct 60 ms 23896 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 5 ms 12376 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 4 ms 12472 KB Output is correct
6 Correct 4 ms 12520 KB Output is correct
7 Correct 5 ms 12380 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 4 ms 12276 KB Output is correct
22 Correct 4 ms 12380 KB Output is correct
23 Correct 4 ms 12380 KB Output is correct
24 Correct 4 ms 12380 KB Output is correct
25 Correct 5 ms 12380 KB Output is correct
26 Correct 4 ms 12380 KB Output is correct
27 Correct 5 ms 12380 KB Output is correct
28 Correct 5 ms 12380 KB Output is correct
29 Correct 4 ms 12380 KB Output is correct
30 Correct 5 ms 12380 KB Output is correct
31 Correct 4 ms 12532 KB Output is correct
32 Correct 4 ms 12380 KB Output is correct
33 Correct 4 ms 12380 KB Output is correct
34 Correct 4 ms 12384 KB Output is correct
35 Correct 4 ms 12380 KB Output is correct
36 Correct 4 ms 12380 KB Output is correct
37 Correct 4 ms 12380 KB Output is correct
38 Correct 4 ms 12452 KB Output is correct
39 Correct 55 ms 22780 KB Output is correct
40 Correct 60 ms 22872 KB Output is correct
41 Correct 70 ms 22816 KB Output is correct
42 Correct 58 ms 22620 KB Output is correct
43 Correct 58 ms 22868 KB Output is correct
44 Correct 64 ms 22876 KB Output is correct
45 Correct 38 ms 21476 KB Output is correct
46 Correct 35 ms 21868 KB Output is correct
47 Correct 60 ms 22872 KB Output is correct
48 Correct 57 ms 23028 KB Output is correct
49 Correct 59 ms 23048 KB Output is correct
50 Correct 61 ms 22840 KB Output is correct
51 Correct 63 ms 22356 KB Output is correct
52 Correct 56 ms 22864 KB Output is correct
53 Correct 68 ms 23120 KB Output is correct
54 Correct 61 ms 23120 KB Output is correct
55 Correct 75 ms 22100 KB Output is correct
56 Correct 50 ms 21852 KB Output is correct
57 Correct 33 ms 21340 KB Output is correct
58 Correct 42 ms 21472 KB Output is correct
59 Correct 60 ms 22876 KB Output is correct
60 Correct 65 ms 23124 KB Output is correct
61 Correct 69 ms 23072 KB Output is correct
62 Correct 64 ms 23044 KB Output is correct
63 Correct 65 ms 22876 KB Output is correct
64 Correct 63 ms 22872 KB Output is correct
65 Correct 60 ms 22064 KB Output is correct
66 Correct 59 ms 23632 KB Output is correct
67 Correct 43 ms 21336 KB Output is correct
68 Correct 55 ms 22104 KB Output is correct
69 Correct 66 ms 23128 KB Output is correct
70 Correct 63 ms 23128 KB Output is correct
71 Correct 45 ms 22000 KB Output is correct
72 Correct 69 ms 23124 KB Output is correct
73 Correct 64 ms 21760 KB Output is correct
74 Correct 62 ms 22324 KB Output is correct
75 Correct 65 ms 23888 KB Output is correct
76 Correct 43 ms 22100 KB Output is correct
77 Correct 54 ms 23152 KB Output is correct
78 Correct 61 ms 23928 KB Output is correct
79 Correct 43 ms 22316 KB Output is correct
80 Correct 35 ms 22028 KB Output is correct
81 Correct 48 ms 23368 KB Output is correct
82 Correct 39 ms 22608 KB Output is correct
83 Correct 55 ms 23920 KB Output is correct
84 Correct 60 ms 23896 KB Output is correct
85 Correct 62 ms 23632 KB Output is correct
86 Correct 73 ms 24228 KB Output is correct
87 Correct 55 ms 23644 KB Output is correct
88 Correct 64 ms 24664 KB Output is correct
89 Correct 43 ms 22108 KB Output is correct
90 Correct 71 ms 24880 KB Output is correct
91 Correct 55 ms 23376 KB Output is correct
92 Correct 53 ms 23036 KB Output is correct
93 Correct 67 ms 24656 KB Output is correct
94 Correct 69 ms 24660 KB Output is correct
95 Correct 71 ms 24404 KB Output is correct
96 Correct 70 ms 24620 KB Output is correct
97 Correct 68 ms 24660 KB Output is correct
98 Correct 77 ms 23636 KB Output is correct
99 Correct 52 ms 23484 KB Output is correct
100 Correct 53 ms 23388 KB Output is correct
101 Correct 63 ms 24924 KB Output is correct
102 Correct 58 ms 24916 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 5 ms 12376 KB Output is correct
3 Correct 4 ms 12376 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 4 ms 12472 KB Output is correct
6 Correct 4 ms 12520 KB Output is correct
7 Correct 5 ms 12380 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 5 ms 12380 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 5 ms 12380 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 5 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 4 ms 12276 KB Output is correct
22 Correct 4 ms 12380 KB Output is correct
23 Correct 4 ms 12380 KB Output is correct
24 Correct 4 ms 12380 KB Output is correct
25 Correct 5 ms 12380 KB Output is correct
26 Correct 4 ms 12380 KB Output is correct
27 Correct 5 ms 12380 KB Output is correct
28 Correct 5 ms 12380 KB Output is correct
29 Correct 4 ms 12380 KB Output is correct
30 Correct 5 ms 12380 KB Output is correct
31 Correct 4 ms 12532 KB Output is correct
32 Correct 4 ms 12380 KB Output is correct
33 Correct 4 ms 12380 KB Output is correct
34 Correct 4 ms 12384 KB Output is correct
35 Correct 4 ms 12380 KB Output is correct
36 Correct 4 ms 12380 KB Output is correct
37 Correct 4 ms 12380 KB Output is correct
38 Correct 4 ms 12452 KB Output is correct
39 Correct 55 ms 22780 KB Output is correct
40 Correct 60 ms 22872 KB Output is correct
41 Correct 70 ms 22816 KB Output is correct
42 Correct 58 ms 22620 KB Output is correct
43 Correct 58 ms 22868 KB Output is correct
44 Correct 64 ms 22876 KB Output is correct
45 Correct 38 ms 21476 KB Output is correct
46 Correct 35 ms 21868 KB Output is correct
47 Correct 60 ms 22872 KB Output is correct
48 Correct 57 ms 23028 KB Output is correct
49 Correct 59 ms 23048 KB Output is correct
50 Correct 61 ms 22840 KB Output is correct
51 Correct 63 ms 22356 KB Output is correct
52 Correct 56 ms 22864 KB Output is correct
53 Correct 68 ms 23120 KB Output is correct
54 Correct 61 ms 23120 KB Output is correct
55 Incorrect 89 ms 51996 KB Output isn't correct
56 Halted 0 ms 0 KB -