제출 #809983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
809983		PixelCat	식물 비교 (IOI20_plants)	C++14	19 / 100	746 ms	39704 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 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);
        if(itr == pos.end()) {
            itr = pos.begin();
        }
        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;
    }
    void out() {
        for(auto &i:pos) cerr << i << " ";
        cerr << "\n";
        for(auto &i:d) cerr << "(" << i.F << ", " << i.S << ") ";
        cerr << "\n";
    }
} aya;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    int add[MAXN * 4 + 10];
    pii mn[MAXN * 4 + 10];  // {value, index}
    void pull(int id) {
        mn[id] = min(mn[L(id)], mn[R(id)]);
        mn[id].F += add[id];
    }
    void build(int id, int l, int r, int *owo) {
        add[id] = 0;
        if(l == r) {
            add[id] = owo[l];
            mn[id] = pii(owo[l], 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].F += 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);
    }
    pii find_min(int id, int l, int r, int L, int R) {
        if(L > R) {
            return min(
                find_min(0, 0, n - 1, L, n - 1),
                find_min(0, 0, n - 1, 0, R)
            );
        }
        if(l >= L && r <= R) return mn[id];
        int m = (l + r) / 2;
        pii res(n * 8, -1);
        if(L <= m) res = min(res, find_min(L(id), l, m, L, R));
        if(R > m)  res = min(res, find_min(R(id), m + 1, r, L, R));
        res.F += add[id];
        return res;
    }
    void kill_all() {
        pii res = find_min(0, 0, n - 1, 0, n - 1);
        while(res.F == 0) {
            aya.insert(res.S);
            range_add(0, 0, n - 1, res.S, res.S, n * 888);
            res = find_min(0, 0, n - 1, 0, n - 1);
        }
    }
} seg;

int r[MAXN + 10];
int rk[MAXN + 10];
int pos[MAXN + 10];
int pl[MAXN + 10];
int pr[MAXN + 10];
int sl[MAXN + 10];
int sr[MAXN + 10];

void init(int __k, vector<int> __r) {
    k = __k;
    n = sz(__r);
    For(i, 0, n - 1) r[i] = __r[i];
    
    seg.build(0, 0, n - 1, r);
    seg.kill_all();
    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.kill_all();
        rk[idx] = rank;
        pos[rank] = idx;
    }

    seg.build(0, 0, n - 1, rk);
    For(rank, 1, n) {
        int idx = pos[rank];
        pii owo;
        owo = seg.find_min(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n);
        pl[idx] = (owo.F <= n ? owo.S : idx);
        owo = seg.find_min(0, 0, n - 1, (idx + 1) % n, (idx + k - 1) % n);
        pr[idx] = (owo.F <= n ? owo.S : idx);
        sl[idx] = dist(pl[idx], idx);
        sr[idx] = dist(idx, pr[idx]);
        seg.range_add(0, 0, n - 1, idx, idx, n * 888);
    }

    // For(i, 0, n - 1) cerr << rk[i] << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << pl[i] << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << sl[i] << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << pr[i] << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << sr[i] << " \n"[i == n - 1];
    
    For(_, 1, 49) {
        For(rank, 1, n) {
            int idx = pos[rank];
            sl[idx] += sl[pl[idx]];
            pl[idx] = pl[pl[idx]];
            sr[idx] += sr[pr[idx]];
            pr[idx] = pr[pr[idx]];
        }
        // For(i, 0, n - 1) cerr << sr[i] << " \n"[i == n - 1];
    }
}
 
int compare_plants(int x, int y) {
    if(rk[x] > rk[y]) return -compare_plants(y, x);
    bool uwu = false;
    if(sl[x] >= n - 1) uwu = true;
    if(sl[x] >= dist(y, x)) uwu = true;
    if(sr[x] >= dist(x, y)) uwu = true;
    return (uwu ? (rk[x] < rk[y] ? 1 : -1) : 0);
}

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