oj.uz

Submission #82954

# Submission time Handle Problem Language Result Execution time Memory
82954 2018-11-03T08:25:25 Z teomrn Growing Trees (BOI11_grow) C++14
100 / 100
 296 ms 42916 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, 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;
}

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 180 ms 6392 KB Output is correct
2 Correct 256 ms 7968 KB Output is correct
3 Correct 127 ms 9336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9336 KB Output is correct
2 Correct 6 ms 9336 KB Output is correct
3 Correct 7 ms 9336 KB Output is correct
4 Correct 4 ms 9336 KB Output is correct
5 Correct 109 ms 9336 KB Output is correct
6 Correct 129 ms 9336 KB Output is correct
7 Correct 11 ms 9336 KB Output is correct
8 Correct 39 ms 9336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 9468 KB Output is correct
2 Correct 154 ms 10512 KB Output is correct
3 Correct 4 ms 10512 KB Output is correct
4 Correct 107 ms 11148 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 12428 KB Output is correct
2 Correct 148 ms 13408 KB Output is correct
3 Correct 16 ms 13408 KB Output is correct
4 Correct 131 ms 14612 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 18348 KB Output is correct
2 Correct 246 ms 20024 KB Output is correct
3 Correct 42 ms 20024 KB Output is correct
4 Correct 125 ms 21412 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 22704 KB Output is correct
2 Correct 289 ms 24236 KB Output is correct
3 Correct 117 ms 25256 KB Output is correct
4 Correct 51 ms 25256 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 27408 KB Output is correct
2 Correct 175 ms 29004 KB Output is correct
3 Correct 133 ms 30052 KB Output is correct
4 Correct 44 ms 30052 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 32436 KB Output is correct
2 Correct 258 ms 33140 KB Output is correct
3 Correct 76 ms 34844 KB Output is correct
4 Correct 126 ms 35548 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 36780 KB Output is correct
2 Correct 248 ms 38460 KB Output is correct
3 Correct 281 ms 40552 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 42916 KB Output is correct