oj.uz

답안 #495467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
495467 2021-12-18T17:53:25 Z danikoynov 푸드 코트 (JOI21_foodcourt) C++14
0 / 100
 730 ms 71804 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] != ((int)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 ++)
      |                     ~~^~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 56748 KB Output is correct
2 Correct 100 ms 57124 KB Output is correct
3 Incorrect 104 ms 56928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 595 ms 69488 KB Output is correct
2 Correct 461 ms 68384 KB Output is correct
3 Correct 590 ms 70100 KB Output is correct
4 Correct 551 ms 68936 KB Output is correct
5 Correct 509 ms 68788 KB Output is correct
6 Correct 730 ms 70712 KB Output is correct
7 Correct 100 ms 58252 KB Output is correct
8 Correct 106 ms 58016 KB Output is correct
9 Correct 725 ms 71720 KB Output is correct
10 Correct 710 ms 71804 KB Output is correct
11 Correct 587 ms 69960 KB Output is correct
12 Correct 609 ms 69848 KB Output is correct
13 Correct 586 ms 69864 KB Output is correct
14 Correct 614 ms 69912 KB Output is correct
15 Correct 604 ms 69920 KB Output is correct
16 Correct 597 ms 69888 KB Output is correct
17 Correct 604 ms 69936 KB Output is correct
18 Correct 613 ms 69864 KB Output is correct
19 Correct 605 ms 69964 KB Output is correct
20 Correct 603 ms 69852 KB Output is correct
21 Correct 632 ms 69952 KB Output is correct
22 Correct 646 ms 69900 KB Output is correct
23 Correct 651 ms 69956 KB Output is correct
24 Correct 668 ms 69876 KB Output is correct
25 Correct 471 ms 69764 KB Output is correct
26 Correct 482 ms 70024 KB Output is correct
27 Incorrect 457 ms 70204 KB Output isn't correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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