제출 #801378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
801378		becaido	식물 비교 (IOI20_plants)	C++17	100 / 100	769 ms	79724 KiB

plants

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "plants.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#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;
}

/*
in1
4 3 2
0 1 1 2
0 2
1 2
out1
1
-1

in2
4 2 2
0 1 0 1
0 3
1 3
out2
1
0

ex1(4 1 2 5 3 0)
6 4 5
1 3 2 0 1 3
0 1
3 4
2 0
1 3
5 2

6 2 5
0 1 1 0 0 1
0 1
3 4
2 0
1 3
5 2
*/

#ifdef WAIMAI
int main() {
    int n, k, q;
    vector<int> r;
    vector<int> x;
    vector<int> y;
    vector<int> answer;
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	return 0;
}
#endif

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25