Submission #304448

#	Time	Username	Problem	Language	Result	Execution time	Memory
304448		mhy908	Comparing Plants (IOI20_plants)	C++14	100 / 100	1897 ms	35276 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long LL;
const LL LLINF=1e18;

int n, k;
vector<int> vc1, vc2;

struct LAZY_SEG{
    LL tree[1600010], lazy[1600010];
    void prop(int point, int s, int e){
        if(s==e)tree[point]+=lazy[point];
        else{
            lazy[point*2]+=lazy[point];
            lazy[point*2+1]+=lazy[point];
        }
        lazy[point]=0;
    }
    void eat(int point){
        tree[point]=min(tree[point*2]+lazy[point*2], tree[point*2+1]+lazy[point*2+1]);
    }
    void init(){
        memset(tree, 0, sizeof tree);
        memset(lazy, 0, sizeof lazy);
    }
    void alter(int point, int s, int e, int a, int b, LL val){
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            lazy[point]+=val;
            return;
        }
        prop(point, s, e);
        alter(point*2, s, (s+e)/2, a, b, val);
        alter(point*2+1, (s+e)/2+1, e, a, b, val);
        eat(point);
    }
    int argmin(int point, int s, int e){
        if(tree[point]+lazy[point]>0)return -1;
        if(s==e)return s;
        prop(point, s, e);
        int ret=argmin(point*2, s, (s+e)/2);
        if(ret<0)ret=argmin(point*2+1, (s+e)/2+1, e);
        eat(point);
        return ret;
    }
}seg;

int stk[400010], re;

vector<int> calc(vector<int> vc){
    vector<int> ret;
    ret.resize(vc.size());
    re=0;
    seg.init();
    for(int i=0; i<2*n; i++){
        seg.alter(1, 0, 2*n-1, i, i, (LL)vc[i]);
    }
    for(int i=1; i<=2*n; i++){
        int x;
        while(1){
            x=seg.argmin(1, 0, 2*n-1);
            if(x>=0)break;
            seg.alter(1, 0, 2*n-1, stk[re], 2*n-1, -1);
            re--;
        }
        ret[x]=i;
        seg.alter(1, 0, 2*n-1, x, x, LLINF);
        seg.alter(1, 0, 2*n-1, x-k+1, x-1, -1);
        if(x-k+1<0)stk[++re]=2*n+x-k;
    }
    return ret;
}

void init(int _k, vector<int> r){
	n=r.size(); k=_k;
	for(int i=0; i<n; i++)r.eb(r[i]);
	vc1=calc(r);
	for(int i=0; i<2*n; i++)r[i]=k-1-r[i];
	vc2=calc(r);
}

int compare_plants(int x, int y){
	if(x>y)return -compare_plants(y, x);
    if(vc1[x]>vc1[y]||vc2[x+n]<vc2[y])return -1;
    if(vc2[x]>vc2[y]||vc1[x+n]<vc1[y])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