제출 #82954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82954		teomrn	Growing Trees (BOI11_grow)	C++14	100 / 100	296 ms	42916 KiB

grow

#include <bits/stdc++.h>
using namespace std;

mt19937 rnd((long long)new char);

typedef struct Treap * Arbore;
typedef pair <Arbore, Arbore> Paa;
Arbore NIL;
struct Treap {
    int vmin, vmax, g, val, prio, lazy;
    Arbore st, dr;
    Treap(int val) : lazy(0), vmin(val), vmax(val), g(1), val(val), prio(rnd()), st(NIL), dr(NIL) { }
    void recalc() {
        vmin = (st != NIL ? st->vmin + st->lazy : val);
        vmax = (dr != NIL ? dr->vmax + dr->lazy : val);
        g = 1 + st->g + dr->g;
    }
    void pass() {
        val += lazy;
        if (st != NIL)
            st->lazy += lazy;
        if (dr != NIL)
            dr->lazy += lazy;
        lazy = 0;
    }
};

Arbore join(Arbore a, Arbore b)
{
    if (a == NIL)
        return b;
    if (b == NIL)
        return a;
    a->pass();
    b->pass();
    if (a->prio > b->prio) {
        a->dr = join(a->dr, b);
        a->recalc();
        return a;
    }
    b->st = join(a, b->st);
    b->recalc();
    return b;
}

Paa split_by_count(Arbore a, int nr)
{
    if (a == NIL)
        return { NIL, NIL };
    a->pass();
    if (a->st->g >= nr) {
        auto x = split_by_count(a->st, nr);
        a->st = NIL;
        a->recalc();
        return { x.first, join(x.second, a) };
    }
    auto x = split_by_count(a->dr, nr - a->st->g - 1);
    a->dr = NIL;
    a->recalc();
    return { join(a, x.first), x.second };
}

Paa split_by_value(Arbore a, int nr)
{
    if (a == NIL)
        return { NIL, NIL };
    a->pass();
    if (a->val > nr) {
        auto x = split_by_value(a->st, nr);
        a->st = NIL;
        a->recalc();
        return { x.first, join(x.second, a) };
    }
    auto x = split_by_value(a->dr, nr);
    a->dr = NIL;
    a->recalc();
    return { join(a, x.first), x.second };
}

Arbore increment(Arbore a, int hmin, int nr)
{
    if (a->vmax < hmin)
        return a;
    Arbore mici, ok, mari, proc;
    tie(mici, proc) = split_by_value(a, hmin - 1);
    tie(ok, mari) = split_by_count(proc, nr);
    ok->lazy++;
    int inv = ok->vmax;
    auto good = split_by_value(ok, inv);
    auto bad = split_by_value(mari, inv);
    mici = join(mici, good.first);
    mici = join(mici, bad.first);
    mici = join(mici, good.second);
    mici = join(mici, bad.second);
    return mici;
}

Arbore query(Arbore a, int hmin, int hmax)
{
    auto mici = split_by_value(a, hmax);
    auto si_mai_mici = split_by_value(mici.first, hmin - 1);
    cout << si_mai_mici.second->g << '\n';
    Arbore ans = join(si_mai_mici.first, si_mai_mici.second);
    return join(ans, mici.second);
}

int main()
{
    int n, m, c;
    NIL = new Treap(0);
    Arbore root = NIL;
    NIL->g = 0;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;

    vector <int> v(n);
    for (auto & i : v)
        cin >> i;
    sort(v.begin(), v.end());

    for (auto i : v)
        root = join(root, new Treap(i));

    while (m--) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'C')
            root = query(root, a, b);
        else
            root = increment(root, b, a);
    }

    return 0;
}

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

grow.cpp: In constructor 'Treap::Treap(int)':
grow.cpp:10:35: warning: 'Treap::lazy' will be initialized after [-Wreorder]
     int vmin, vmax, g, val, prio, lazy;
                                   ^~~~
grow.cpp:10:9: warning:   'int Treap::vmin' [-Wreorder]
     int vmin, vmax, g, val, prio, lazy;
         ^~~~
grow.cpp:12:5: warning:   when initialized here [-Wreorder]
     Treap(int val) : lazy(0), vmin(val), vmax(val), g(1), val(val), prio(rnd()), st(NIL), dr(NIL) { }
     ^~~~~
grow.cpp: In function 'int main()':
grow.cpp:109:15: warning: unused variable 'c' [-Wunused-variable]
     int n, m, c;
               ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10