Submission #622594

#	Time	Username	Problem	Language	Result	Execution time	Memory
622594		wiwiho	Comparing Plants (IOI20_plants)	C++14	100 / 100	1749 ms	85024 KiB

plants

#include "plants.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MAX = 1e6;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

void waassert(bool t){
    if(t) return;
    exit(0);
}

int n, K;
vector<int> rec;
vector<bool> use;

struct Node{
    int mn = 0, pos = 0, tag = 0;
};

Node operator+(Node a, Node b){
    Node c;
    c.mn = min(a.mn, b.mn);
    if(a.mn == c.mn) c.pos = a.pos;
    else c.pos = b.pos;
    return c;
}

vector<Node> st;
#define lc 2 * id + 1
#define rc 2 * id + 2

void build(vector<int>& o, int L = 0, int R = n - 1, int id = 0){
    if(L == R){
        st[id].mn = o[L];
        st[id].pos = L;
        return;
    }
    int M = (L + R) / 2;
    build(o, L, M, lc);
    build(o, M + 1, R, rc);
    st[id] = st[lc] + st[rc];
}

void addtag(int v, int id){
    st[id].tag += v;
    st[id].mn += v;
}

void push(int id){
    addtag(st[id].tag, lc);
    addtag(st[id].tag, rc);
    st[id].tag = 0;
}

void _modify(int l, int r, int v, int L = 0, int R = n - 1, int id = 0){
    if(l <= L && R <= r){
        addtag(v, id);
        return;
    }
    push(id);
    int M = (L + R) / 2;
    if(r <= M) _modify(l, r, v, L, M, lc);
    else if(l > M) _modify(l, r, v, M + 1, R, rc);
    else{
        _modify(l, r, v, L, M, lc);
        _modify(l, r, v, M + 1, R, rc);
    }
    st[id] = st[lc] + st[rc];
}

void modify(int l, int r, int v){
    l = (l % n + n) % n;
    r = (r % n + n) % n;
    if(l <= r) _modify(l, r, v);
    else{
        _modify(l, n - 1, v);
        _modify(0, r, v);
    }
}

Node _query(int l, int r, int L = 0, int R = n - 1, int id = 0){
    if(l <= L && R <= r) return st[id];
    push(id);
    int M = (L + R) / 2;
    if(r <= M) return _query(l, r, L, M, lc);
    else if(l > M) return _query(l, r, M + 1, R, rc);
    else return _query(l, r, L, M, lc) + _query(l, r, M + 1, R, rc);
}

Node query(int l, int r){
    l = (l % n + n) % n;
    r = (r % n + n) % n;
    if(l <= r) return _query(l, r);
    else{
        return _query(l, n - 1) + _query(0, r);
    }
}

void _print(int L = 0, int R = n - 1, int id = 0){
    if(L == R){
        cerr << st[id].mn << " ";
        return;
    }
    push(id);
    int M = (L + R) / 2;
    _print(L, M, lc);
    _print(M + 1, R, rc);
}

void print(){
    _print();
    cerr << "\n";
}

int getdis(int l, int r){
    l = (l % n + n) % n;
    r = (r % n + n) % n;
    if(l == r) return n;
    if(l > r) r += n;
    return r - l;
}

set<int> zero;
set<pii> sep;
vector<int> rk;

void solve(int _rk){
    
    while(st[0].mn == 0){
        int pos = st[0].pos;
        modify(pos, pos, MAX);

        if(zero.empty()){
            zero.insert(pos);
            sep.insert(mp(n, pos));
            continue;
        }
        
        auto it = zero.lower_bound(pos);
        if(it == zero.end()) it = zero.begin();
        int nxt = *it;
        int lst = it == zero.begin() ? *zero.rbegin() : *prev(it);
        sep.erase(mp(getdis(lst, nxt), nxt));
        sep.insert(mp(getdis(lst, pos), pos));
        sep.insert(mp(getdis(pos, nxt), nxt));
        zero.insert(pos);
    }

    int pos = sep.rbegin()->S;
    if(zero.size() == 1){
        sep.clear();
        zero.clear();
    }
    else{
        auto it = zero.lower_bound(pos);
        int nxt = next(it) == zero.end() ? *zero.begin() : *next(it);
        int lst = it == zero.begin() ? *zero.rbegin() : *prev(it);
        sep.erase(mp(getdis(lst, pos), pos));
        sep.erase(mp(getdis(pos, nxt), nxt));
        sep.insert(mp(getdis(lst, nxt), nxt));
        zero.erase(pos);
    }

    use[pos] = true;
    rk[pos] = _rk;
    modify(pos - K + 1, pos - 1, -1);
}

vector<int> ans;
vector<vector<ll>> ri, le;

void init(int k, vector<int> _r){
    K = k;
    rec = _r;
    n = rec.size();
    st.resize(4 * n);
    use.resize(n);
    rk.resize(n);
    ans.resize(n);
    build(rec);

    for(int i = n - 1; i >= 0; i--){
        solve(i);
    }

    le.resize(20, vector<ll>(n));
    ri.resize(20, vector<ll>(n));
    
    {
        vector<int> tmp(n, 1);
        build(tmp);
    }
    vector<int> pos(n);
    for(int i = 0; i < n; i++) pos[rk[i]] = i;
    
    for(int i = 0; i < n; i++){
        Node tmp = query(pos[i] + 1, pos[i] + k - 1);
        if(tmp.mn != 1){
            int nxt = tmp.pos;
            ri[0][pos[i]] = getdis(pos[i], nxt);
            /*cerr << "right " << pos[i] << " : " << nxt << "\n";
            cerr << pos[i] + 1 << " " << pos[i] + k - 1 << "\n";*/
        }
        tmp = query(pos[i] - k + 1, pos[i] - 1);
        if(tmp.mn != 1){
            int nxt = tmp.pos;
            le[0][pos[i]] = getdis(nxt, pos[i]);
            /*cerr << "left " << pos[i] << " : " << nxt << "\n";
            cerr << pos[i] - k + 1 << " " << pos[i] - 1 << "\n";*/
        }
        modify(pos[i], pos[i], -i);
    }
    
    for(int i = 1; i < 20; i++){
        for(int j = 0; j < n; j++){
            int nxt = j - le[i - 1][j];
            nxt = (nxt % n + n) % n;
            le[i][j] = le[i - 1][j] + le[i - 1][nxt];

            nxt = j + ri[i - 1][j];
            nxt = nxt % n;
            ri[i][j] = ri[i - 1][j] + ri[i - 1][nxt];
        }
    }

    /*cerr << "rank ";
    printv(rk, cerr);
    cerr << "left ";
    printv(le[0], cerr);
    cerr << "right ";
    printv(ri[0], cerr);*/

}

bool checkgreater(int x, int y){
    // right
    {
        int dis = getdis(x, y);
        ll tmp = 0;
        int now = x;
        for(int i = 19; i >= 0; i--){
            if(tmp + ri[i][now] >= dis - K + 1) continue;
            tmp += ri[i][now];
            now = (x + tmp) % n;
        }
        if(tmp < dis - K + 1){
            tmp += ri[0][now];
            now = (x + tmp) % n;
        }
        if(tmp >= dis - K + 1 && rk[now] > rk[y]) return true;
    }
    // left
    {
        int dis = getdis(y, x);
        ll tmp = 0;
        int now = x;
        for(int i = 19; i >= 0; i--){
            if(tmp + le[i][now] >= dis - K + 1) continue;
            tmp += le[i][now];
            now = ((x - tmp) % n + n) % n;
        }
        if(tmp < dis - K + 1){
            tmp += le[0][now];
            now = ((x - tmp) % n + n) % n;
        }
        if(tmp >= dis - K + 1 && rk[now] > rk[y]) return true;
    }
    return false;
}

int compare_plants(int x, int y){
    if(checkgreater(x, y)) return 1;
    if(checkgreater(y, x)) return -1;
    return 0;
}

• 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