Submission #951118

#	Time	Username	Problem	Language	Result	Execution time	Memory
951118		Trisanu_Das	Comparing Plants (IOI20_plants)	C++17	44 / 100	2017 ms	87808 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200100
int pos[N], cnt, K;
int mval[4*N], mpl[4*N], mpr[4*N], l[4*N],r[4*N], sub[4*N];
set<int> mop[4*N];
void pd(int n) {
    if(sub[n]) {
        mval[n]-=sub[n];
        if(l[n]!=r[n])
            sub[n*2]+=sub[n],
            sub[n*2+1]+=sub[n];
        sub[n] = 0;
    }
}
vector<int> R;
void upd(int n) {
    if(l[n]==r[n]) return;
    if(mval[2*n]!=mval[2*n+1])
        if(mval[2*n]>mval[2*n+1])
            mval[n] = mval[2*n+1],
            mpl[n] = mpl[2*n+1],
            mpr[n] = mpr[2*n+1],
            mop[n] = mop[2*n+1];
        else mval[n] = mval[2*n],
            mop[n] = mop[2*n],
            mpl[n] = mpl[2*n],
            mpr[n] = mpr[2*n];
    else {
        mpl[n] = mpl[2*n];
        mpr[n]=mpr[2*n+1];
        mval[n]=mval[2*n];
        mop[n]=mop[2*n];
        for(auto i: mop[2*n+1]) {
            mop[n].insert(i);
        }
        if(mpl[2*n+1]-mpr[2*n]<K)
            mop[n].erase(mpl[2*n+1]);
        if(mpl[2*n]+(int)R.size()-mpr[2*n+1]<K)
            mop[n].erase(mpl[2*n]);
    }
}
int n;
void build(int i, int lp, int rp) {
    l[i] = lp, r[i] = rp;
    if(lp==rp)
        mval[i] = R[lp-1], mpl[i]=mpr[i]=lp,mop[i].insert(lp);
    else build(i*2,lp,(lp+rp)>>1),
        build(i*2+1,(lp+rp+2)>>1,rp),
        upd(i);
}
void update(int i, int rl, int rr, int v) {
    pd(i);
    if(rl<=l[i]&&r[i]<=rr)
        return (void)(sub[i]-=v,pd(i));
    if(rl<=r[i*2])
        update(i*2,rl,rr,v);
    if(r[i*2]<rr)
        update(i*2+1,rl,rr,v);
    pd(i*2);
    pd(i*2+1);
    upd(i);
}
void UPD(int x) {
    if(x<K) {
        update(1,1,x,-1);
        update(1,n-K+x+1,n,-1);
    } else {
        update(1,x-K+1,x,-1);
    }
    update(1,x,x,1e9);
}
void init(int k, vector<int> _r) {
    n = _r.size();
    K=k;
    R = _r;
    build(1,1,n);
    for(int i = 0; i < n;) {
        ++cnt;
        set<int> x = mop[1];
        i+=x.size();
        for(auto i: x)
            pos[i-1] = cnt, UPD(i), cerr << i << ' ';
        cerr << '\n';
    }
	return;
}
int compare_plants(int x, int y) {
    if(pos[x]<pos[y])
        return 1;
    if(pos[x]-pos[y])
        return -1;
    return 0;
}

• 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