oj.uz

Submission #192706

# Submission time Handle Problem Language Result Execution time Memory
192706 2020-01-15T06:57:49 Z imeimi2000 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 1704 ms 28344 KB 
#include <bits/stdc++.h>
#define fs first
#define se second
using namespace std;
typedef pair<int, int> pii;

const int inf = 1e9 + 1;
const int rinf = inf + inf;
const int linf = -1;

int n, l;

namespace LCT {
    struct node {
        int L, R, P;
        int cnt, sum;
    } ns[300010];
    void set_cnt(int x, int v) {
        ns[x].cnt = ns[x].sum = v;
    }
    void update(int x) {
        ns[x].sum = ns[x].cnt;
        if (ns[x].L) ns[x].sum += ns[ns[x].L].sum;
        if (ns[x].R) ns[x].sum += ns[ns[x].R].sum;
    }
    bool is_root(int x) {
        return ns[x].P == 0 || ns[ns[x].P].L != x && ns[ns[x].P].R != x;
    }
    void rotate(int x) {
        int p = ns[x].P;
        if (ns[p].L == x) {
            ns[p].L = ns[x].R;
            if (ns[p].L) ns[ns[p].L].P = p;
            ns[x].R = p;
        }
        else {
            ns[p].R = ns[x].L;
            if (ns[p].R) ns[ns[p].R].P = p;
            ns[x].L = p;
        }
        ns[x].P = ns[p].P;
        ns[p].P = x;
        if (ns[x].P) {
            if (ns[ns[x].P].L == p) ns[ns[x].P].L = x;
            else if (ns[ns[x].P].R == p) ns[ns[x].P].R = x;
        }
        update(p);
        update(x);
    }
    void splay(int x) {
        while (!is_root(x)) {
            int p = ns[x].P;
            if (!is_root(p)) {
                if ((ns[ns[p].P].L == p) == (ns[p].L == x)) rotate(p);
                else rotate(x);
            }
            rotate(x);
        }
    }
    int access(int x) {
        splay(x);
        ns[x].R = 0;
        update(x);
        int ret = x;
        while (ns[x].P) {
            ret = ns[x].P;
            splay(ret);
            ns[ret].R = x;
            update(ret);
            splay(x);
        }
        return ret;
    }
    void link(int x, int p) {
        access(x);
        access(p);
        ns[x].L = p;
        ns[p].P = x;
        update(x);
    }
    void cut(int x) {
        access(x);
        ns[ns[x].L].P = 0;
        ns[x].L = 0;
        update(x);
    }
    int get_sum(int x) {
        access(x);
        return ns[x].sum;
    }
    int par(int x) {
        access(x);
        x = ns[x].L;
        while (ns[x].R) x = ns[x].R;
        return x;
    }
}

int pos[150010];
set<pii> sp;
int dl, dr;

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    dl = n + n + 1;
    pos[n + 1] = linf - l;
    dr = n + n + 2;
    pos[n + 2] = rinf - l;
    for (int i = 1; i <= n; ++i) {
        LCT::set_cnt(i, 1);
        pos[i] = X[i - 1];
        sp.emplace(pos[i], i);
        sp.emplace(pos[i] + l, i + n);
    }
    sp.emplace(linf, dl);
    sp.emplace(rinf, dr);
    pii prv = pii(-1, -1);
    for (pii i : sp) {
        if (prv.se != -1) {
            if (prv.se <= n) {
                LCT::link(prv.se, prv.se + n);
            }
            else {
                LCT::link(prv.se, i.se);
            }
        }
        prv = i;
    }
}

int update(int p, int v) {
    ++p;
    vector<int> need;
    need.push_back(p + n);
    auto it1 = prev(sp.find(pii(pos[p], p)));
    auto it2 = prev(sp.find(pii(pos[p] + l, p + n)));
    if (it1->se > n) need.push_back(it1->se);
    if (it2->se > n) need.push_back(it2->se);
    sp.erase(pii(pos[p], p));
    sp.erase(pii(pos[p] + l, p + n));
    pos[p] = v;
    sp.emplace(pos[p], p);
    sp.emplace(pos[p] + l, p + n);
    auto it3 = prev(sp.find(pii(pos[p], p)));
    auto it4 = prev(sp.find(pii(pos[p] + l, p + n)));
    if (it3->se > n) need.push_back(it3->se);
    if (it4->se > n) need.push_back(it4->se);
    sort(need.begin(), need.end());
    need.erase(unique(need.begin(), need.end()), need.end());
    for (int i : need) LCT::cut(i);
    for (int i : need) {
        int x = pos[i - n] + l;
        auto it = sp.upper_bound(pii(x, i));
        int p = it->se;
        LCT::link(i, p);
    }
    return LCT::get_sum(dl);
}

Compilation message

elephants.cpp: In function 'bool LCT::is_root(int)':
elephants.cpp:27:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         return ns[x].P == 0 || ns[ns[x].P].L != x && ns[ns[x].P].R != x;
                                ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 ms 376 KB Output is correct
7 Correct 107 ms 3656 KB Output is correct
8 Correct 114 ms 4480 KB Output is correct
9 Correct 279 ms 9564 KB Output is correct
10 Correct 190 ms 9380 KB Output is correct
11 Correct 191 ms 9312 KB Output is correct
12 Correct 410 ms 9476 KB Output is correct
13 Correct 216 ms 9164 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 ms 376 KB Output is correct
7 Correct 107 ms 3656 KB Output is correct
8 Correct 114 ms 4480 KB Output is correct
9 Correct 279 ms 9564 KB Output is correct
10 Correct 190 ms 9380 KB Output is correct
11 Correct 191 ms 9312 KB Output is correct
12 Correct 410 ms 9476 KB Output is correct
13 Correct 216 ms 9164 KB Output is correct
14 Correct 298 ms 5196 KB Output is correct
15 Correct 214 ms 5936 KB Output is correct
16 Correct 596 ms 10088 KB Output is correct
17 Correct 635 ms 13136 KB Output is correct
18 Correct 759 ms 13052 KB Output is correct
19 Correct 277 ms 13256 KB Output is correct
20 Correct 868 ms 13124 KB Output is correct
21 Correct 636 ms 13104 KB Output is correct
22 Correct 297 ms 12692 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 0 ms 376 KB Output is correct
7 Correct 107 ms 3656 KB Output is correct
8 Correct 114 ms 4480 KB Output is correct
9 Correct 279 ms 9564 KB Output is correct
10 Correct 190 ms 9380 KB Output is correct
11 Correct 191 ms 9312 KB Output is correct
12 Correct 410 ms 9476 KB Output is correct
13 Correct 216 ms 9164 KB Output is correct
14 Correct 298 ms 5196 KB Output is correct
15 Correct 214 ms 5936 KB Output is correct
16 Correct 596 ms 10088 KB Output is correct
17 Correct 635 ms 13136 KB Output is correct
18 Correct 759 ms 13052 KB Output is correct
19 Correct 277 ms 13256 KB Output is correct
20 Correct 868 ms 13124 KB Output is correct
21 Correct 636 ms 13104 KB Output is correct
22 Correct 297 ms 12692 KB Output is correct
23 Correct 1118 ms 28344 KB Output is correct
24 Correct 1128 ms 28320 KB Output is correct
25 Correct 981 ms 28316 KB Output is correct
26 Correct 546 ms 28316 KB Output is correct
27 Correct 552 ms 28164 KB Output is correct
28 Correct 690 ms 5696 KB Output is correct
29 Correct 708 ms 5700 KB Output is correct
30 Correct 693 ms 5780 KB Output is correct
31 Correct 698 ms 5704 KB Output is correct
32 Correct 668 ms 27836 KB Output is correct
33 Correct 662 ms 27100 KB Output is correct
34 Correct 707 ms 27964 KB Output is correct
35 Correct 629 ms 28280 KB Output is correct
36 Correct 1018 ms 27860 KB Output is correct
37 Correct 1497 ms 28216 KB Output is correct
38 Correct 757 ms 26972 KB Output is correct
39 Correct 678 ms 28024 KB Output is correct
40 Correct 722 ms 26872 KB Output is correct
41 Correct 1704 ms 27896 KB Output is correct
42 Correct 1655 ms 27964 KB Output is correct