제출 #809521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
809521		PixelCat	Comparing Plants (IOI20_plants)	C++14	0 / 100	1 ms	232 KiB

plants

#include "plants.h"
 
#ifdef NYAOWO
#include "grader.cpp"
#endif
 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
 
const int MAXN = 200'000;
 
int n, k;
int rk[MAXN + 10];
 
int dist(int s, int t) {
    if(s <= t) return t - s;
    else return t - s + n;
}

struct Ayaya {
    set<int> pos;
    set<pii> d;
    pii find(int x) {
        auto itr = pos.upper_bound(x);
        auto itl = pos.lower_bound(x);
        if(itl == pos.begin()) {
            itl = prev(pos.end());
        } else {
            itl = prev(itl);
        }
        return pii(*itl, *itr);
    }
    void insert(int x) {
        if(sz(pos) == 0) {
            pos.insert(x);
            d.emplace(0, x);
            return;
        }
        int l, r; tie(l, r) = find(x);
        d.erase(pii(dist(l, r), r));
        d.insert(pii(dist(l, x), x));
        d.insert(pii(dist(x, r), r));
        pos.insert(x);
    }
    void erase(int x) {
        if(sz(pos) == 1) {
            pos.clear(); d.clear();
            return;
        }
        int l, r; tie(l, r) = find(x);
        d.erase(pii(dist(l, x), x));
        d.erase(pii(dist(x, r), r));
        d.insert(pii(dist(l, r), r));
        pos.erase(x);
    }
    int pop() {
        int i = prev(d.end())->S;
        erase(i);
        return i;
    }
} aya;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    int add[MAXN * 4 + 10];
    int mn[MAXN * 4 + 10];
    void pull(int id) {
        mn[id] = min(mn[L(id)], mn[R(id)]) + add[id];
    }
    void build(int id, int l, int r, vector<int> &owo) {
        add[id] = 0;
        if(l == r) {
            add[id] = mn[id] = owo[l];
            return;
        }
        int m = (l + r) / 2;
        build(L(id), l, m, owo);
        build(R(id), m + 1, r, owo);
        pull(id);
    }
    void range_add(int id, int l, int r, int L, int R, int val) {
        if(L > R) {
            range_add(0, 0, n - 1, L, n - 1, val);
            range_add(0, 0, n - 1, 0, R, val);
            return;
        }
        if(l >= L && r <= R) {
            add[id] += val; mn[id] += val;
            return;
        }
        int m = (l + r) / 2;
        if(L <= m) range_add(L(id), l, m, L, R, val);
        if(R > m)  range_add(R(id), m + 1, r, L, R, val);
        pull(id);
    }
    int kill_min(int id, int l, int r, int accu) {
        accu += add[id];
        if(l == r) {
            if(accu == 0) {
                add[id] = mn[id] = n * 888;
                return l;
            }
            return -1;
        }
        int m = (l + r) / 2;
        int res;
        if(mn[L(id)] < mn[R(id)]) {
            res = kill_min(L(id), l, m, accu);
        } else {
            res = kill_min(R(id), m + 1, r, accu);
        }
        pull(id);
        return res;
    }
    void kill() {
        int res = kill_min(0, 0, n - 1, 0);
        while(res != -1) {
            aya.insert(res);
            res = kill_min(0, 0, n - 1, 0);
        }
    }
} seg;
 
void init(int __k, vector<int> r) {
    k = __k;
    n = sz(r);
    seg.build(0, 0, n - 1, r);
    seg.kill();
    For(rank, 1, n) {
        int idx = aya.pop();
        seg.range_add(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n, -1);
        seg.range_add(0, 0, n - 1, idx, idx, n * 888);
        seg.kill();
        rk[idx] = rank;
    }
}
 
int compare_plants(int x, int y) {
    if(rk[x] < rk[y]) return 1;
    return -1;
}

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