oj.uz

Submission #82958

# Submission time Handle Problem Language Result Execution time Memory
82958 2018-11-03T08:43:27 Z teomrn Growing Trees (BOI11_grow) C++14
100 / 100
 292 ms 6204 KB 
#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;
    tie(mici, ok) = split_by_value(a, hmin - 1);
    tie(ok, mari) = split_by_count(ok, 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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 5068 KB Output is correct
2 Correct 273 ms 5068 KB Output is correct
3 Correct 137 ms 5068 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 5 ms 5068 KB Output is correct
3 Correct 11 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 140 ms 5068 KB Output is correct
6 Correct 163 ms 5068 KB Output is correct
7 Correct 10 ms 5068 KB Output is correct
8 Correct 43 ms 5068 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 5068 KB Output is correct
2 Correct 129 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 72 ms 5068 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 5068 KB Output is correct
2 Correct 151 ms 5068 KB Output is correct
3 Correct 17 ms 5068 KB Output is correct
4 Correct 130 ms 5068 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 5068 KB Output is correct
2 Correct 260 ms 5068 KB Output is correct
3 Correct 41 ms 5068 KB Output is correct
4 Correct 111 ms 5068 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 5068 KB Output is correct
2 Correct 266 ms 5068 KB Output is correct
3 Correct 129 ms 5068 KB Output is correct
4 Correct 42 ms 5068 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 5120 KB Output is correct
2 Correct 177 ms 5308 KB Output is correct
3 Correct 144 ms 5308 KB Output is correct
4 Correct 43 ms 5308 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 5308 KB Output is correct
2 Correct 277 ms 5308 KB Output is correct
3 Correct 71 ms 5820 KB Output is correct
4 Correct 121 ms 5820 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 5820 KB Output is correct
2 Correct 254 ms 5820 KB Output is correct
3 Correct 292 ms 5820 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 6204 KB Output is correct