제출 #494355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494355		danikoynov	푸드 코트 (JOI21_foodcourt)	C++14	0 / 100	468 ms	524292 KiB

foodcourt

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

using namespace std;
const int maxn = 250010;
typedef long long ll;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct Treap
{
    struct Node
    {
        ll pr, key, sz, key_sum, gr;
        Node *l, *r;

        Node(ll _key, ll _gr)
        {
            gr = _gr;
            sz = 1;
            pr = rand();
            key = _key;
            key_sum = _key;
            l = r = NULL;
        }

        void prll()
        {
            if (l) l -> prll();
            cout << key << " ";
            if (r) r -> prll();
        }
        void con()
        {
            sz = 1;
            key_sum = key;
            if (l)
            {
                sz += l -> sz;
                key_sum += l -> key_sum;
            }
            if (r)
            {
                sz += r -> sz;
                key_sum += r -> key_sum;
            }
        }
    };

    Node *root = NULL;

    void SplitSum(Node *T, Node *&L, Node *&R, ll qsum)
    {
        if (T == NULL)
        {
            L = R = NULL;
            return;
        }

        ll sum = T -> key;
        if (T -> l)
            sum += T -> l -> key_sum;

        if (qsum >= sum)
        {
            L = T;
            SplitSum(T -> r, L -> r, R, qsum - sum);
        }
        else
        {
            R = T;
            SplitSum(T -> l, L, R -> l, qsum);
        }

        T -> con();
    }

        void SplitSize(Node *T, Node *&L, Node *&R, ll qsize)
    {
        ///cout << "again" << endl;
        if (T == NULL)
        {
            L = R = NULL;
            return;
        }

        ll _sz = 1;
        if (T -> l)
            _sz += T -> l -> sz;

        ///cout << T -> key << " " << _sz << endl;

        if (qsize >= _sz)
        {
            L = T;
            SplitSize(T -> r, L -> r, R, qsize - _sz);
        }
        else
        {
            ///cout << "hey" << endl;
            R = T;
            SplitSize(T -> l, L, R -> l, qsize);
        }

        T -> con();
    }

    void Merge(Node *&T, Node *L, Node *R)
    {
        if (L == NULL && R == NULL)
        {
            T = NULL;
            return;
        }

        if (L == NULL)
        {
            T = R;
            return;
        }

        if (R == NULL)
        {
            T = L;
            return;
        }

        if (L -> pr > R -> pr)
        {
            T = L;
            Merge(T -> r, L -> r, R);
        }
        else
        {
            T = R;
            Merge(T -> l, L, R -> l);
        }

        T -> con();
    }

    void Insert(ll _key, ll _gr)
    {
        ///cout << "Insert" << endl;
        Node *M = new Node(_key, _gr);
        Merge(root, root, M);
    }

    void Erase(ll k)
    {
        if (root == NULL)
            return;
        if (root -> key_sum < k)
        {
            root = NULL;
            return;
        }


        Node *L, *M, *R;
        SplitSum(root, L, R, k);

        if (L != NULL)
            k -= L -> key_sum;
        if (k != 0)
        {
            SplitSize(R, M, R, 1);
            M -> key -= k;
            M -> key_sum -= k;
            Merge(R, M, R);
        }
        root = R;
    }


    ll query(ll pos)
    {
        if (root == NULL)
        return 0;
        if (root -> key_sum < pos)
            return 0;
        ///cout << root -> key_sum << endl;
        Node *L, *M, *R;
        SplitSum(root, L, R, pos - 1);
        SplitSize(R, M, R, 1);
        ll ans = M -> gr;
        Merge(R, M, R);
        Merge(root, L, R);
        return ans;
    }
};

ll n, m, q;
Treap tree[4 * maxn];
vector < pair < ll, ll > >lazy_add[4 * maxn], lazy_rem[4 * maxn];

void push_lazy(ll root, ll left, ll right)
{
    if (left != right)
    {
        for (ll j = 0; j < lazy_add[root].size(); j ++)
        {
            lazy_add[root * 2].push_back(lazy_add[root][j]);
            lazy_add[root * 2 + 1].push_back(lazy_add[root][j]);
        }
        for (ll j = 0; j < lazy_rem[root].size(); j ++)
        {
            lazy_rem[root * 2].push_back(lazy_rem[root][j]);
            lazy_rem[root * 2 + 1].push_back(lazy_rem[root][j]);
        }
    }
    if (left == right)
    {
    for (ll j = 0; j < lazy_add[root].size(); j ++)
    {
        tree[root].Insert(lazy_add[root][j].first, lazy_add[root][j].second);
    }

    for (ll j = 0; j < lazy_rem[root].size(); j ++)
    {
        ///cout << "here" << endl;
        ///cout << left << " " << right << endl;
        tree[root].Erase(lazy_rem[root][j].first);
    }
    }
      lazy_add[root].clear();
    lazy_rem[root].clear();
    ///if (tree[root].root != NULL)
       /// cout << left << " - " << right << " " << tree[root].root -> key_sum << endl;
}
void update_range(ll root, ll left, ll right,
                  ll qleft, ll qright, ll c, ll k, ll t)
{

    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;
///cout << root << " - " << left << " " << right << " " << qleft << " " << qright << " " <<c << " " << k << endl;
    if (left >= qleft && right <= qright)
    {
        ///cout << "here" << endl;
        if (t == 1)
        lazy_add[root].push_back({k, c});
        else
        lazy_rem[root].push_back({k, c});
        push_lazy(root, left, right);
        return;
    }

    ll mid = (left + right) / 2;
    update_range(root * 2, left, mid, qleft, qright, c, k, t);
    update_range(root * 2 + 1, mid + 1, right, qleft, qright, c, k, t);

}

ll poll_query(ll root, ll left, ll right, ll idx, ll k)
{
    push_lazy(root, left, right);
    if (left == right)
        return tree[root].query(k);

    ll mid = (left + right) / 2;
    if (idx <= mid)
    {
        return poll_query(root * 2, left, mid, idx, k);
    }
    else
    {
        return poll_query(root * 2 + 1, mid + 1, right, idx, k);
    }
}
void solve()
{
    cin >> n >> m >> q;
    for (ll i = 1; i <= q; i ++)
    {
        ll type;
        cin >> type;
        if (type == 1)
        {
            ll l, r, c, k;
            cin >> l >> r >> c >> k;
            update_range(1, 1, n, l, r, c, k, 1);
        }
        else
        if (type == 2)
        {
            ll l, r, k;
            cin >> l >> r >> k;
            update_range(1, 1, n, l, r, 0, k, 2);
        }
        else
        {
            ll a, b;
            cin >> a >> b;
            ll ans = poll_query(1, 1, n, a, b);
            cout << ans << endl;;
        }
    }
}
int main()
{
    speed();
    solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp: In function 'void push_lazy(ll, ll, ll)':
foodcourt.cpp:205:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |         for (ll j = 0; j < lazy_add[root].size(); j ++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:210:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |         for (ll j = 0; j < lazy_rem[root].size(); j ++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:218:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |     for (ll j = 0; j < lazy_add[root].size(); j ++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:223:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for (ll j = 0; j < lazy_rem[root].size(); j ++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11