oj.uz

답안 #495465

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
495465 2021-12-18T17:48:07 Z danikoynov 푸드 코트 (JOI21_foodcourt) C++14
0 / 100
 846 ms 78008 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);

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

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;
                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)
        {
            node nd = st.tree[1];
            if (nd.minx > 0)
                break;
            int pos = nd.min_idx;
            ans[ask[pos][ptr[pos]].second] = aq.c;
            ll val = inf;
            if (ptr[pos] != ask[pos].size() - 1)
            {
                val = ask[pos][ptr[pos] + 1].first
                 - ask[pos][ptr[pos]].first;
            }
            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:244:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<add_query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  244 |     for (int i = 0; i < vq.size(); i ++)
      |                     ~~^~~~~~~~~~~
foodcourt.cpp:256:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  256 |             if (ptr[pos] != ask[pos].size() - 1)
      |                 ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 53324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 53324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 57976 KB Output is correct
2 Correct 111 ms 58176 KB Output is correct
3 Incorrect 96 ms 57928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 582 ms 74928 KB Output is correct
2 Correct 496 ms 72516 KB Output is correct
3 Correct 639 ms 75912 KB Output is correct
4 Correct 555 ms 73336 KB Output is correct
5 Correct 563 ms 73240 KB Output is correct
6 Correct 756 ms 76844 KB Output is correct
7 Correct 103 ms 62340 KB Output is correct
8 Correct 108 ms 62076 KB Output is correct
9 Correct 846 ms 77700 KB Output is correct
10 Correct 732 ms 78008 KB Output is correct
11 Correct 634 ms 75948 KB Output is correct
12 Correct 651 ms 76020 KB Output is correct
13 Correct 629 ms 75928 KB Output is correct
14 Correct 596 ms 75968 KB Output is correct
15 Correct 602 ms 75868 KB Output is correct
16 Correct 623 ms 76000 KB Output is correct
17 Correct 642 ms 75940 KB Output is correct
18 Correct 615 ms 75884 KB Output is correct
19 Correct 624 ms 75984 KB Output is correct
20 Correct 636 ms 75844 KB Output is correct
21 Correct 596 ms 75888 KB Output is correct
22 Correct 601 ms 75828 KB Output is correct
23 Correct 627 ms 75984 KB Output is correct
24 Correct 615 ms 75912 KB Output is correct
25 Correct 457 ms 75284 KB Output is correct
26 Correct 487 ms 75776 KB Output is correct
27 Incorrect 470 ms 76012 KB Output isn't correct

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 53324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 153 ms 59252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 53324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 53324 KB Output isn't correct
2 Halted 0 ms 0 KB -