oj.uz

Submission #801386

# Submission time Handle Problem Language Result Execution time Memory
801386 2023-08-02T05:51:00 Z becaido Comparing Plants (IOI20_plants) C++17
100 / 100
 868 ms 78796 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int INF = 1e9;
const int SIZE = 2e5 + 5;
const int H = __lg(SIZE);

int n, k;
int a[SIZE], rnk[SIZE], id[SIZE];

set<int> s;
set<pair<int, int>> d;
int dis(int l, int r) {
    return l < r ? r - l : r + n - l;
}
void ins(int i) {
    if (s.size() == 0) {
        s.insert(i);
        d.emplace(dis(i, i), i);
        return;
    }
    auto it = s.lower_bound(i);
    int l = (it == s.begin() ? *s.rbegin() : *prev(it));
    int r = (it == s.end() ? *s.begin() : *it);
    d.erase({dis(l, r), r});
    s.insert(i);
    d.emplace(dis(l, i), i);
    d.emplace(dis(i, r), r);
}
void del(int i) {
    if (s.size() == 1) {
        s.clear();
        d.clear();
        return;
    }
    auto it = s.lower_bound(i);
    int l = (it == s.begin() ? *s.rbegin() : *prev(it));
    int r = (next(it) == s.end() ? *s.begin() : *next(it));
    d.erase({dis(l, i), i});
    d.erase({dis(i, r), r});
    s.erase(i);
    d.emplace(dis(l, r), r);
}
vector<int> getv() {
    vector<int> v;
    for (auto it = d.rbegin(); it != d.rend(); it++) {
        auto [delta, i] = *it;
        if (delta < k) break;
        v.pb(i);
    }
    for (int i : v) del(i);
    return v;
}

struct Tree {
    int mn[SIZE * 4], lazy[SIZE * 4];
    void build() {
        build(1, 0, n - 1);
    }
    void build(int pos, int l, int r) {
        if (l == r) {
            mn[pos] = k - 1 - a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(lpos, l, mid);
        build(rpos, mid + 1, r);
        mn[pos] = min(mn[lpos], mn[rpos]);
    }
    void push(int pos, int l, int r) {
        mn[pos] += lazy[pos];
        if (l < r) {
            lazy[lpos] += lazy[pos];
            lazy[rpos] += lazy[pos];
        }
        lazy[pos] = 0;
    }
    void pull(int pos, int l, int r) {
        int mid = (l + r) / 2;
        push(lpos, l, mid);
        push(rpos, mid + 1, r);
        mn[pos] = min(mn[lpos], mn[rpos]);
    }
    void upd(int l, int r, int x) {
        if (l <= r) upd(1, l, r, 0, n - 1, x);
        else {
            upd(l, n - 1, x);
            upd(0, r, x);
        }
    }
    void upd(int pos, int l, int r, int L, int R, int x) {
        if (l == L && r == R) {
            lazy[pos] += x;
            return;
        }
        push(pos, L, R);
        int mid = (L + R) / 2;
        if (r <= mid) upd(lpos, l, r, L, mid, x);
        else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
        else {
            upd(lpos, l, mid, L, mid, x);
            upd(rpos, mid + 1, r, mid + 1, R, x);
        }
        pull(pos, L, R);
    }
    void dfs() {
        dfs(1, 0, n - 1);
    }
    void dfs(int pos, int l, int r) {
        push(pos, l, r);
        if (mn[pos] != 0) return;
        if (l == r) {
            ins(l);
            mn[pos] = INF;
            return;
        }
        int mid = (l + r) / 2;
        dfs(lpos, l, mid);
        dfs(rpos, mid + 1, r);
        pull(pos, l, r);
    }
} tree;

struct Tree2 {
    int mnp[SIZE * 4];
    bool vs[SIZE];
    int cmp(int i, int j) {
        if (vs[i] || vs[j]) return vs[i] ? j : i;
        return rnk[i] < rnk[j] ? i : j;
    }
    void build() {
        build(1, 0, n - 1);
    }
    void build(int pos, int l, int r) {
        if (l == r) {
            mnp[pos] = l;
            return;
        }
        int mid = (l + r) / 2;
        build(lpos, l, mid);
        build(rpos, mid + 1, r);
        mnp[pos] = cmp(mnp[lpos], mnp[rpos]);
    }
    void upd(int p) {
        upd(1, 0, n - 1, p);
    }
    void upd(int pos, int l, int r, int p) {
        if (l == r) {
            vs[p] = 1;
            return;
        }
        int mid = (l + r) / 2;
        if (p <= mid) upd(lpos, l, mid, p);
        else upd(rpos, mid + 1, r, p);
        mnp[pos] = cmp(mnp[lpos], mnp[rpos]);
    }
    int que(int l, int r) {
        int re;
        if (l <= r) re = que(1, l, r, 0, n - 1);
        else re = cmp(que(1, 0, r, 0, n - 1), que(1, l, n - 1, 0, n - 1));
        if (vs[re]) re = -1;
        return re;
    }
    int que(int pos, int l, int r, int L, int R) {
        if (l == L && r == R) return mnp[pos];
        int mid = (L + R) / 2;
        if (r <= mid) return que(lpos, l, r, L, mid);
        if (l > mid) return que(rpos, l, r, mid + 1, R);
        return cmp(que(lpos, l, mid, L, mid), que(rpos, mid + 1, r, mid + 1, R));
    }
} tree2;

int L[SIZE][H + 1], R[SIZE][H + 1];
int ld[SIZE][H + 1], rd[SIZE][H + 1];
void init(int _k, vector<int> _r) {
    n = _r.size();
    k = _k;
    FOR (i, 0, n - 1) a[i] = _r[i];
    tree.build();
    for (int t = 0, cnt = 0; cnt < n; t++) {
        tree.dfs();
        auto v = getv();
        cnt += v.size();
        for (int i : v) {
            rnk[i] = t;
            int l = i - k + 1, r = i - 1;
            if (l < 0) l += n;
            if (r < 0) r += n;
            tree.upd(l, r, -1);
        }
    }
    iota(id, id + n, 0);
    sort(id, id + n, [](int l, int r) {
        return rnk[l] < rnk[r];
    });
    tree2.build();
    FOR (t, 0, n - 1) {
        int l, r, i, j;
        i = id[t];
        l = i - k + 1, r = i - 1;
        if (l < 0) l += n;
        if (r < 0) r += n;
        L[i][0] = j = tree2.que(l, r);
        if (j != -1) ld[i][0] = dis(j, i);
        l = i + 1, r = i + k - 1;
        if (l >= n) l -= n;
        if (r >= n) r -= n;
        R[i][0] = j = tree2.que(l, r);
        if (j != -1) rd[i][0] = dis(i, j);
        tree2.upd(i);
    }
    FOR (j, 1, H) FOR (i, 0, n - 1) {
        int to;
        to = L[i][j - 1];
        if (to == -1) L[i][j] = -1;
        else {
            L[i][j] = L[to][j - 1];
            ld[i][j] = min(n, ld[i][j - 1] + ld[to][j - 1]);
        }
        to = R[i][j - 1];
        if (to == -1) R[i][j] = -1;
        else {
            R[i][j] = R[to][j - 1];
            rd[i][j] = min(n, rd[i][j - 1] + rd[to][j - 1]);
        }
    }
}

bool check(int x, int y) {
    if (rnk[x] >= rnk[y]) return 0;
    int pos, sum;
    pos = x, sum = 0;
    for (int i = H; i >= 0; i--) if (L[pos][i] != -1 && rnk[L[pos][i]] <= rnk[y]) {
        sum += ld[pos][i];
        pos = L[pos][i];
    }
    if (sum >= dis(y, x)) return 1;
    pos = x, sum = 0;
    for (int i = H; i >= 0; i--) if (R[pos][i] != -1 && rnk[R[pos][i]] <= rnk[y]) {
        sum += rd[pos][i];
        pos = R[pos][i];
    }
    if (sum >= dis(x, y)) return 1;
    return 0;
}
int compare_plants(int x, int y) {
    return rnk[x] < rnk[y] && check(x, y) ? -1 : rnk[x] > rnk[y] && check(y, x) ? 1 : 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 44 ms 3148 KB Output is correct
7 Correct 98 ms 10096 KB Output is correct
8 Correct 606 ms 78796 KB Output is correct
9 Correct 603 ms 70624 KB Output is correct
10 Correct 581 ms 65540 KB Output is correct
11 Correct 560 ms 63848 KB Output is correct
12 Correct 512 ms 64060 KB Output is correct
13 Correct 387 ms 55180 KB Output is correct
14 Correct 631 ms 73932 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 78 ms 4904 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 79 ms 4816 KB Output is correct
11 Correct 76 ms 4624 KB Output is correct
12 Correct 69 ms 5000 KB Output is correct
13 Correct 76 ms 4816 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 78 ms 4904 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 79 ms 4816 KB Output is correct
11 Correct 76 ms 4624 KB Output is correct
12 Correct 69 ms 5000 KB Output is correct
13 Correct 76 ms 4816 KB Output is correct
14 Correct 113 ms 9932 KB Output is correct
15 Correct 740 ms 69304 KB Output is correct
16 Correct 115 ms 9968 KB Output is correct
17 Correct 719 ms 69304 KB Output is correct
18 Correct 515 ms 62340 KB Output is correct
19 Correct 652 ms 71556 KB Output is correct
20 Correct 713 ms 69300 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 64 ms 3820 KB Output is correct
4 Correct 558 ms 75480 KB Output is correct
5 Correct 607 ms 70604 KB Output is correct
6 Correct 640 ms 69448 KB Output is correct
7 Correct 689 ms 69316 KB Output is correct
8 Correct 868 ms 69304 KB Output is correct
9 Correct 615 ms 69856 KB Output is correct
10 Correct 585 ms 71168 KB Output is correct
11 Correct 414 ms 55164 KB Output is correct
12 Correct 690 ms 73996 KB Output is correct
13 Correct 514 ms 59360 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 15 ms 1016 KB Output is correct
8 Correct 14 ms 1112 KB Output is correct
9 Correct 13 ms 1036 KB Output is correct
10 Correct 16 ms 1028 KB Output is correct
11 Correct 14 ms 1032 KB Output is correct
12 Correct 18 ms 1108 KB Output is correct
13 Correct 16 ms 1016 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 703 ms 69504 KB Output is correct
7 Correct 660 ms 69324 KB Output is correct
8 Correct 674 ms 69300 KB Output is correct
9 Correct 737 ms 69300 KB Output is correct
10 Correct 493 ms 69908 KB Output is correct
11 Correct 525 ms 69300 KB Output is correct
12 Correct 454 ms 75472 KB Output is correct
13 Correct 517 ms 70732 KB Output is correct
14 Correct 605 ms 69448 KB Output is correct
15 Correct 629 ms 69240 KB Output is correct
16 Correct 532 ms 72880 KB Output is correct
17 Correct 484 ms 69572 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 44 ms 3148 KB Output is correct
7 Correct 98 ms 10096 KB Output is correct
8 Correct 606 ms 78796 KB Output is correct
9 Correct 603 ms 70624 KB Output is correct
10 Correct 581 ms 65540 KB Output is correct
11 Correct 560 ms 63848 KB Output is correct
12 Correct 512 ms 64060 KB Output is correct
13 Correct 387 ms 55180 KB Output is correct
14 Correct 631 ms 73932 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 3 ms 692 KB Output is correct
21 Correct 78 ms 4904 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 3 ms 724 KB Output is correct
24 Correct 79 ms 4816 KB Output is correct
25 Correct 76 ms 4624 KB Output is correct
26 Correct 69 ms 5000 KB Output is correct
27 Correct 76 ms 4816 KB Output is correct
28 Correct 113 ms 9932 KB Output is correct
29 Correct 740 ms 69304 KB Output is correct
30 Correct 115 ms 9968 KB Output is correct
31 Correct 719 ms 69304 KB Output is correct
32 Correct 515 ms 62340 KB Output is correct
33 Correct 652 ms 71556 KB Output is correct
34 Correct 713 ms 69300 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 64 ms 3820 KB Output is correct
38 Correct 558 ms 75480 KB Output is correct
39 Correct 607 ms 70604 KB Output is correct
40 Correct 640 ms 69448 KB Output is correct
41 Correct 689 ms 69316 KB Output is correct
42 Correct 868 ms 69304 KB Output is correct
43 Correct 615 ms 69856 KB Output is correct
44 Correct 585 ms 71168 KB Output is correct
45 Correct 414 ms 55164 KB Output is correct
46 Correct 690 ms 73996 KB Output is correct
47 Correct 514 ms 59360 KB Output is correct
48 Correct 0 ms 340 KB Output is correct
49 Correct 1 ms 340 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 0 ms 340 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 2 ms 468 KB Output is correct
54 Correct 15 ms 1016 KB Output is correct
55 Correct 14 ms 1112 KB Output is correct
56 Correct 13 ms 1036 KB Output is correct
57 Correct 16 ms 1028 KB Output is correct
58 Correct 14 ms 1032 KB Output is correct
59 Correct 18 ms 1108 KB Output is correct
60 Correct 16 ms 1016 KB Output is correct
61 Correct 60 ms 3784 KB Output is correct
62 Correct 101 ms 10180 KB Output is correct
63 Correct 649 ms 71424 KB Output is correct
64 Correct 666 ms 69504 KB Output is correct
65 Correct 679 ms 69328 KB Output is correct
66 Correct 658 ms 69304 KB Output is correct
67 Correct 714 ms 69300 KB Output is correct
68 Correct 577 ms 69864 KB Output is correct
69 Correct 625 ms 69220 KB Output is correct
70 Correct 608 ms 75468 KB Output is correct
71 Correct 622 ms 70688 KB Output is correct
72 Correct 670 ms 69440 KB Output is correct
73 Correct 668 ms 69208 KB Output is correct
74 Correct 640 ms 70608 KB Output is correct
75 Correct 527 ms 69856 KB Output is correct