oj.uz

Submission #495471

# Submission time Handle Problem Language Result Execution time Memory
495471 2021-12-18T18:26:37 Z danikoynov Food Court (JOI21_foodcourt) C++14
45 / 100
 990 ms 71792 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;
const int maxn = 250010;
const ll inf = 1e17;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


struct segment_tree_modified
{

    pair < ll, ll > lazy[4 * maxn];
    ll tree[4 * maxn];

    pair < ll, ll > merge_lazy(pair < ll, ll > p1, pair < ll, ll > p2)
    {
        if (p1.second > p2.first)
        {
            return {p1.first, p1.second - p2.first + p2.second};
        }
        else
        {
            return {p1.first - p1.second + p2.first, p2.second};
        }
    }
    void push_lazy(int root, int left, int right)
    {
        if (left == right)
        {
            tree[root] = max((ll)(0), tree[root] - lazy[root].first) + lazy[root].second;

        }
        else
        {
            lazy[root * 2] = merge_lazy(lazy[root * 2], lazy[root]);
            lazy[root * 2 + 1] = merge_lazy(lazy[root * 2 + 1], lazy[root]);
        }
        lazy[root] = {0, 0};
    }

    void range_update(int root, int left, int right, int qleft, int qright,
                      pair < ll, ll > val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;
        if (left >= qleft && right <= qright)
        {
            lazy[root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        range_update(root * 2, left, mid, qleft, qright, val);
        range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);
    }

    ll query(int root, int left, int right, int idx)
    {
        ///cout << left << " - " << right << " " << lazy[root].first << " " << lazy[root].second << endl;
        push_lazy(root, left, right);
        if (left == right)
            return tree[root];

        int mid = (left + right) /2;
        if (idx <= mid)
            return query(root * 2, left, mid, idx);
        return query(root * 2 + 1, mid + 1, right, idx);
    }

};

struct node
{
    ll minx, min_idx;

    node()
    {
        minx = inf;
    }
};

node merge_nodes(node nd1, node nd2)
{
    if (nd1.minx < nd2.minx)
        return nd1;
    return nd2;
}

struct segment_tree
{



    ll lazy[4 * maxn];
    node tree[4 * maxn];

    void push_lazy(int root, int left, int right)
    {
        tree[root].minx += lazy[root];
        if (left == right)
            tree[root].min_idx = left;

        if (left != right)
        {
            lazy[root * 2] += lazy[root];
            lazy[root * 2 + 1] += lazy[root];
        }

        lazy[root] = 0;
    }

    void range_update(int root, int left, int right,
                      int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] += val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        range_update(root * 2, left, mid, qleft, qright, val);
        range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);

        tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
    }


    void point_update(int root, int left, int right, int idx, ll val)
    {
        push_lazy(root, left, right);
        if (left == right)
        {
            tree[root].minx = val;
            tree[root].min_idx = left;
            return;
        }

        int mid = (left + right) / 2;
        if (idx <= mid)
            point_update(root * 2, left, mid, idx, val);
        else
            point_update(root * 2 + 1, mid + 1, right, idx, val);
        push_lazy(root * 2, left, mid);
        push_lazy(root * 2 + 1, mid + 1, right);
        tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
    }

    node query(int root, int left, int right, int idx)
    {
        push_lazy(root, left, right);
        if (left == right)
            return tree[root];

        int mid = (left + right) / 2;
        if (idx <= mid)
            return query(root * 2, left, mid, idx);
        return query(root * 2 + 1, mid + 1, right, idx);
    }
};

struct add_query
{
    int l, r, c;
    ll k;

    add_query(int _l, int _r, int _c, ll _k)
    {
        l = _l;
        r = _r;
        c = _c;
        k = _k;
    }
};

segment_tree_modified real_val, add_only;
segment_tree st;

int n, m, q, ans[maxn], ptr[maxn], tf[maxn];
vector < pair < int, int > > ask[maxn];
void solve()
{
    cin >> n >> m >> q;
    vector < add_query > vq;
    for (int i = 1; i <= q; i ++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r, c;
            ll k;
            cin >> l >> r >> c >> k;
            add_query aq(l, r, c, k);
            vq.push_back(aq);
            real_val.range_update(1, 1, n, l, r, {0, k});
            add_only.range_update(1, 1, n, l, r, {0, k});
        }
        else if (type == 2)
        {
            int l, r;
            ll k;
            cin >> l >> r >> k;
            real_val.range_update(1, 1, n, l, r, {k, 0});
        }
        else
        {
            int a;
            ll b;
            tf[i] = 1;
            cin >> a >> b;
            ll val1 = real_val.query(1, 1, n, a);
            ll val2 = add_only.query(1,1,n, a);
            if (val1 >= b)
            {
                ll idx = val2 - val1 + b;
                ///cout << val1 << " - " << val2 << " - " << b << " - " << idx << endl;
                ask[a].push_back({idx, i});
            }
        }
    }

    for (int i = 1; i <= n; i ++)
        sort(ask[i].begin(), ask[i].end());


    for (int i = 1; i <= n; i ++)
    {
        ll val = inf;
        if (!ask[i].empty())
            val = ask[i][0].first;
        st.point_update(1, 1, n, i, val);
    }

    for (int i = 0; i < vq.size(); i ++)
    {
        add_query aq = vq[i];
        st.range_update(1, 1, n, aq.l, aq.r, - aq.k);

        while(true)
        {
            st.push_lazy(1, 1, n);
            node nd = st.tree[1];
            if (nd.minx > 0)
                break;
        ///cout << aq.l << " - " << aq.r << " - " << aq.c << " - " << endl;
        ///cout << nd.minx << " " << nd.min_idx << " " << st.query(1, 1, n, 978).minx << " " << ans[39] << endl;
            int pos = nd.min_idx;
            ans[ask[pos][ptr[pos]].second] = aq.c;

            ///cout << ask[pos][ptr[pos]].second << endl;
            ll val = inf;
            if (ptr[pos] != ((int)ask[pos].size() - 1))
            {
                val = ask[pos][ptr[pos] + 1].first
                 - ask[pos][ptr[pos]].first;
                ///cout << "HERE " << val << endl;
            }
            st.point_update(1, 1, n, nd.min_idx, val + nd.minx);
            ptr[pos] ++;
        }
    }

    for (int i = 1; i <= q; i ++)
        if (tf[i])
            cout << ans[i] << endl;


}

int main()
{
    speed();
    solve();
    return 0;
}
/**

*/

Compilation message

foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:258:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<add_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  258 |     for (int i = 0; i < vq.size(); i ++)
      |                     ~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53316 KB Output is correct
2 Correct 26 ms 53336 KB Output is correct
3 Correct 25 ms 53308 KB Output is correct
4 Correct 30 ms 53396 KB Output is correct
5 Correct 23 ms 53252 KB Output is correct
6 Correct 23 ms 53200 KB Output is correct
7 Correct 30 ms 53336 KB Output is correct
8 Correct 23 ms 53320 KB Output is correct
9 Correct 24 ms 53320 KB Output is correct
10 Correct 24 ms 53352 KB Output is correct
11 Correct 24 ms 53360 KB Output is correct
12 Correct 31 ms 53392 KB Output is correct
13 Correct 23 ms 53288 KB Output is correct
14 Correct 34 ms 53320 KB Output is correct
15 Correct 29 ms 53268 KB Output is correct
16 Correct 32 ms 53300 KB Output is correct
17 Correct 27 ms 53268 KB Output is correct
18 Correct 25 ms 53368 KB Output is correct
19 Correct 26 ms 53328 KB Output is correct
20 Correct 26 ms 53316 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53316 KB Output is correct
2 Correct 26 ms 53336 KB Output is correct
3 Correct 25 ms 53308 KB Output is correct
4 Correct 30 ms 53396 KB Output is correct
5 Correct 23 ms 53252 KB Output is correct
6 Correct 23 ms 53200 KB Output is correct
7 Correct 30 ms 53336 KB Output is correct
8 Correct 23 ms 53320 KB Output is correct
9 Correct 24 ms 53320 KB Output is correct
10 Correct 24 ms 53352 KB Output is correct
11 Correct 24 ms 53360 KB Output is correct
12 Correct 31 ms 53392 KB Output is correct
13 Correct 23 ms 53288 KB Output is correct
14 Correct 34 ms 53320 KB Output is correct
15 Correct 29 ms 53268 KB Output is correct
16 Correct 32 ms 53300 KB Output is correct
17 Correct 27 ms 53268 KB Output is correct
18 Correct 25 ms 53368 KB Output is correct
19 Correct 26 ms 53328 KB Output is correct
20 Correct 26 ms 53316 KB Output is correct
21 Incorrect 24 ms 53304 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 56832 KB Output is correct
2 Correct 122 ms 57052 KB Output is correct
3 Correct 104 ms 56940 KB Output is correct
4 Correct 107 ms 57888 KB Output is correct
5 Correct 139 ms 58184 KB Output is correct
6 Correct 125 ms 58204 KB Output is correct
7 Correct 39 ms 55056 KB Output is correct
8 Correct 40 ms 55048 KB Output is correct
9 Correct 113 ms 58284 KB Output is correct
10 Correct 117 ms 57980 KB Output is correct
11 Correct 123 ms 58260 KB Output is correct
12 Correct 149 ms 57936 KB Output is correct
13 Correct 100 ms 58252 KB Output is correct
14 Correct 132 ms 58696 KB Output is correct
15 Correct 146 ms 59100 KB Output is correct
16 Correct 128 ms 59224 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 69612 KB Output is correct
2 Correct 523 ms 68432 KB Output is correct
3 Correct 715 ms 70148 KB Output is correct
4 Correct 652 ms 68956 KB Output is correct
5 Correct 642 ms 68844 KB Output is correct
6 Correct 895 ms 70712 KB Output is correct
7 Correct 108 ms 58260 KB Output is correct
8 Correct 123 ms 58128 KB Output is correct
9 Correct 892 ms 71792 KB Output is correct
10 Correct 990 ms 71736 KB Output is correct
11 Correct 656 ms 70016 KB Output is correct
12 Correct 712 ms 69972 KB Output is correct
13 Correct 775 ms 69936 KB Output is correct
14 Correct 818 ms 69900 KB Output is correct
15 Correct 726 ms 69920 KB Output is correct
16 Correct 885 ms 69916 KB Output is correct
17 Correct 738 ms 69912 KB Output is correct
18 Correct 723 ms 69896 KB Output is correct
19 Correct 772 ms 69908 KB Output is correct
20 Correct 689 ms 69924 KB Output is correct
21 Correct 712 ms 69988 KB Output is correct
22 Correct 672 ms 69940 KB Output is correct
23 Correct 693 ms 70004 KB Output is correct
24 Correct 689 ms 70164 KB Output is correct
25 Correct 533 ms 69916 KB Output is correct
26 Correct 539 ms 70136 KB Output is correct
27 Correct 535 ms 70328 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53316 KB Output is correct
2 Correct 26 ms 53336 KB Output is correct
3 Correct 25 ms 53308 KB Output is correct
4 Correct 30 ms 53396 KB Output is correct
5 Correct 23 ms 53252 KB Output is correct
6 Correct 23 ms 53200 KB Output is correct
7 Correct 30 ms 53336 KB Output is correct
8 Correct 23 ms 53320 KB Output is correct
9 Correct 24 ms 53320 KB Output is correct
10 Correct 24 ms 53352 KB Output is correct
11 Correct 24 ms 53360 KB Output is correct
12 Correct 31 ms 53392 KB Output is correct
13 Correct 23 ms 53288 KB Output is correct
14 Correct 34 ms 53320 KB Output is correct
15 Correct 29 ms 53268 KB Output is correct
16 Correct 32 ms 53300 KB Output is correct
17 Correct 27 ms 53268 KB Output is correct
18 Correct 25 ms 53368 KB Output is correct
19 Correct 26 ms 53328 KB Output is correct
20 Correct 26 ms 53316 KB Output is correct
21 Correct 112 ms 56832 KB Output is correct
22 Correct 122 ms 57052 KB Output is correct
23 Correct 104 ms 56940 KB Output is correct
24 Correct 107 ms 57888 KB Output is correct
25 Correct 139 ms 58184 KB Output is correct
26 Correct 125 ms 58204 KB Output is correct
27 Correct 39 ms 55056 KB Output is correct
28 Correct 40 ms 55048 KB Output is correct
29 Correct 113 ms 58284 KB Output is correct
30 Correct 117 ms 57980 KB Output is correct
31 Correct 123 ms 58260 KB Output is correct
32 Correct 149 ms 57936 KB Output is correct
33 Correct 100 ms 58252 KB Output is correct
34 Correct 132 ms 58696 KB Output is correct
35 Correct 146 ms 59100 KB Output is correct
36 Correct 128 ms 59224 KB Output is correct
37 Correct 152 ms 58364 KB Output is correct
38 Correct 151 ms 58220 KB Output is correct
39 Correct 38 ms 54896 KB Output is correct
40 Correct 39 ms 54944 KB Output is correct
41 Correct 162 ms 58568 KB Output is correct
42 Correct 148 ms 58596 KB Output is correct
43 Correct 161 ms 58452 KB Output is correct
44 Correct 165 ms 58588 KB Output is correct
45 Correct 154 ms 58500 KB Output is correct
46 Correct 158 ms 58532 KB Output is correct
47 Correct 85 ms 58384 KB Output is correct
48 Correct 151 ms 58488 KB Output is correct
49 Correct 106 ms 57688 KB Output is correct
50 Correct 140 ms 58104 KB Output is correct
51 Correct 171 ms 58480 KB Output is correct
52 Correct 160 ms 58600 KB Output is correct
53 Correct 103 ms 58448 KB Output is correct
54 Correct 124 ms 59204 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53316 KB Output is correct
2 Correct 26 ms 53336 KB Output is correct
3 Correct 25 ms 53308 KB Output is correct
4 Correct 30 ms 53396 KB Output is correct
5 Correct 23 ms 53252 KB Output is correct
6 Correct 23 ms 53200 KB Output is correct
7 Correct 30 ms 53336 KB Output is correct
8 Correct 23 ms 53320 KB Output is correct
9 Correct 24 ms 53320 KB Output is correct
10 Correct 24 ms 53352 KB Output is correct
11 Correct 24 ms 53360 KB Output is correct
12 Correct 31 ms 53392 KB Output is correct
13 Correct 23 ms 53288 KB Output is correct
14 Correct 34 ms 53320 KB Output is correct
15 Correct 29 ms 53268 KB Output is correct
16 Correct 32 ms 53300 KB Output is correct
17 Correct 27 ms 53268 KB Output is correct
18 Correct 25 ms 53368 KB Output is correct
19 Correct 26 ms 53328 KB Output is correct
20 Correct 26 ms 53316 KB Output is correct
21 Incorrect 24 ms 53304 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53316 KB Output is correct
2 Correct 26 ms 53336 KB Output is correct
3 Correct 25 ms 53308 KB Output is correct
4 Correct 30 ms 53396 KB Output is correct
5 Correct 23 ms 53252 KB Output is correct
6 Correct 23 ms 53200 KB Output is correct
7 Correct 30 ms 53336 KB Output is correct
8 Correct 23 ms 53320 KB Output is correct
9 Correct 24 ms 53320 KB Output is correct
10 Correct 24 ms 53352 KB Output is correct
11 Correct 24 ms 53360 KB Output is correct
12 Correct 31 ms 53392 KB Output is correct
13 Correct 23 ms 53288 KB Output is correct
14 Correct 34 ms 53320 KB Output is correct
15 Correct 29 ms 53268 KB Output is correct
16 Correct 32 ms 53300 KB Output is correct
17 Correct 27 ms 53268 KB Output is correct
18 Correct 25 ms 53368 KB Output is correct
19 Correct 26 ms 53328 KB Output is correct
20 Correct 26 ms 53316 KB Output is correct
21 Incorrect 24 ms 53304 KB Output isn't correct
22 Halted 0 ms 0 KB -