답안 #801386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
801386	2023-08-02T05:51:00 Z	becaido	식물 비교 (IOI20_plants)	C++17	100 / 100	868 ms	78796 KB

plants

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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