Submission #321826

#	Time	Username	Problem	Language	Result	Execution time	Memory
321826		grt	Comparing Plants (IOI20_plants)	C++17	44 / 100	523 ms	23532 KiB

plants

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;

#define ST first
#define ND second
#define PB push_back

struct Node {
    int g;
    pi f;
};

const int nax = 200000 + 10, INF = 1e9 + 10;
int n, k;
int val[nax];
int num[nax];
Node T[(1<<19)];

void prop(int x) {
    T[2*x].g += T[x].g;
    T[2*x+1].g += T[x].g;
    T[x].g = 0;
}

void upd(int a, int b, int l, int r, int v, int x) {
    if(a > b) return;
    if(a <= l && r <= b) {
        T[v].g += x;
        return;
    }
    prop(v);
    int mid = (l + r)/2;
    if(a <= mid) upd(a,b,l,mid,v*2,x);
    if(mid < b) upd(a,b,mid+1,r,v*2+1,x);
    T[v].f = min(make_pair(T[2*v].f.ST + T[2*v].g, T[2*v].f.ND), make_pair(T[2*v+1].f.ST + T[2*v+1].g, T[2*v+1].f.ND));
}

void ini(int l, int r, int v) {
    T[v].f.ND = l;
    if(l == r) {
        return;
    }
    int mid = (l + r)/2;
    ini(l,mid,v*2);
    ini(mid+1,r,v*2+1);
}

pi qr() {
    return {T[1].f.ST + T[1].g, T[1].f.ND};
}

set<int>zero;
set<int>candidate;

int d(int a, int b) {
    if(b >= a) return b - a;
    else return b - a + n;
}

void dodaj(int x) {
    if((int)zero.size() == 0) {
        zero.insert(x);
        candidate.insert(x);
        return;
    }
    auto it = zero.lower_bound(x);
    auto it2 = it;
    if(it == zero.end()) it = zero.begin();
    if(it2== zero.begin()) it2 = zero.end();
    it2--;
    if(d(x, (*it)) < k) candidate.erase((*it));
    if(d((*it2), x) >= k) candidate.insert(x);
    zero.insert(x);
}

void usun(int x) {
    candidate.erase(x);
    zero.erase(x);
    if((int)zero.size() == 0) return;
    auto it = zero.lower_bound(x);
    if(it == zero.end()) {
        it = zero.begin();
    }
    candidate.insert((*it));
}

void init(int K, vi r) {
    k = K;
    n = (int)r.size();
    ini(0, n-1,1);
    for(int i = 0; i < n; ++i) {
        upd(i,i,0,n-1,1,r[i]);
    }
    pi w = qr();
    while(w.ST == 0) {
        dodaj(w.ND);
        //zero.insert(w.ND);
        upd(w.ND,w.ND,0,n-1,1,INF);
        w = qr();
    }
    int cur = n;
    for(int step = 0; step < n; ++step) {
        auto it = candidate.begin();
        int x = (*it);
        //cout << x << " ";
        /*
        int x = -1, last = -1;
        for(auto y : zero) {
            if(last != -1) {
                if(y - last >= k) x = y;
            }
            last = y;
        }
        if(x == -1) x = (*zero.begin());
            */
        upd(max(0, x - k + 1), x - 1, 0, n - 1, 1, -1);
        upd(x - k + 1 + n, n - 1, 0, n - 1, 1, -1);
        usun(x);
        //zero.erase(x);
        w = qr();
        while(w.ST == 0) {
            dodaj(w.ND);
            //zero.insert(w.ND);
            upd(w.ND,w.ND,0,n-1,1,INF);
            w = qr();
        }
        num[x] = cur--;
    }
}

int compare_plants(int x, int y) {
    if(num[x] < num[y]) return -1;
    else return 1;
}

//int main() {
 //   init(3, {0, 1, 1, 2});
 //   cout << compare_plants(0, 2) << "\n";
 //   cout << compare_plants(1, 2) << "\n";
//}

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