Submission #430821

#	Time	Username	Problem	Language	Result	Execution time	Memory
430821		Antekb	Comparing Plants (IOI20_plants)	C++14	100 / 100	2015 ms	74408 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
using namespace std;
const int N=(1<<18);
int rtab[N+N], lazy[2*N];
int k;
void prop(int v){
	if(v>=N || !lazy[v])return;
	int l=v+v, r=l+1;
	lazy[l]+=lazy[v];
	lazy[r]+=lazy[v];
	rtab[l]+=lazy[v];
	rtab[r]+=lazy[v];
	lazy[v]=0;
}
void add(int v, int L, int R, int l, int r, int c){
	if(l==L && r==R){
		lazy[v]+=c;
		rtab[v]+=c;
		return;
	}
	int M=(L+R)>>1;
	prop(v);
	if(l<=M)add(2*v, L, M, l, min(M, r), c);
	if(r>M)add(2*v+1, M+1, R, max(l, M+1), r, c);
	rtab[v]=max(rtab[2*v], rtab[2*v+1]);
}
int checkk(){
	if(rtab[1]<k)return -1;
	int v=1;
	while(v<N){
		prop(v);
		if(rtab[2*v]==k)v=2*v;
		else v=2*v+1;
	}
	return v-N;
}
int tab[N+N], lazy2[N+N];
void prop2(int v){
	if(v>=N || !lazy2[v])return;
	int l=v+v, r=l+1;
	lazy2[l]+=lazy2[v];
	lazy2[r]+=lazy2[v];
	tab[l]+=lazy2[v];
	tab[r]+=lazy2[v];
	lazy2[v]=0;
}
void add2(int v, int L, int R, int l, int r, int c){
	if(l==L && r==R){
		lazy2[v]+=c;
		tab[v]+=c;
		return;
	}
	int M=(L+R)>>1;
	prop2(v);
	if(l<=M)add2(2*v, L, M, l, min(M, r), c);
	if(r>M)add2(2*v+1, M+1, R, max(l, M+1), r, c);
	tab[v]=max(tab[2*v], tab[2*v+1]);
}
int getmax(){
	int v=1;
	while(v<N){
		prop2(v);
		if(tab[2*v]>tab[2*v+1])v=2*v;
		else v=v*2+1;
	}
	return v-N;
}
int maks[N+N];
void Set(int i, int val){
	for(i+=N, maks[i]=val, i>>=1; i; i>>=1){
		maks[i]=max(maks[2*i], maks[2*i+1]);
	}
}
int find(int l, int r){
	r++;
	int ans=0;
	for( l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1)ans=max(maks[l++], ans);
		if(r&1)ans=max(maks[--r], ans);
	}
	return ans;
}
vector<int> kol, gdzie;
const int K=18;
long long Left[K][N], Right[K][N];
int n;
void init(int _k, std::vector<int> r) {
    n=r.size();
    k=_k-1;
    for(int i=0; i<n; i++){
    	rtab[N+i]=k-r[i];
    }
    for(int i=N-1; i>0; i--){
    	rtab[i]=max(rtab[i+i], rtab[i+i+1]);
	}
	//cerr<<rtab[1]<<" "<<k<<"\n";
	gdzie.resize(n);
	for(int i=0; i<n; i++){
		//cerr<<i<<"\n";
		int t=checkk();
		while(t!=-1){
			//cerr<<t<<"\n";
			add(1, 0, N-1, t, t, -N);
			add2(1, 0, N-1, t, t, N);
			if(t<n-1)add2(1, 0, N-1, t+1, min(n-1, t+k), -1);
			if(t+k>=n)add2(1, 0, N-1, 0, t+k-n, -1);
			t=checkk();
		}
		t=getmax();
		assert(tab[t+N]==N);
		//cerr<<t<<"q\n";
		add2(1, 0, N-1, t, t, -N);
		if(t)add(1, 0, N-1, max(t-k, 0), t-1, 1);
		if(t<k)add(1, 0, N-1, n+t-k, n-1, 1);
		if(t<n-1)add2(1, 0, N-1, t+1, min(n-1, t+k), 1);
		if(t+k>=n)add2(1, 0, N-1, 0, t+k-n, 1);
		gdzie[t]=kol.size();
		kol.pb(t);
	}
	for(int i=n-1; i>=0; i--){
		int a=0;
		int t=kol[i];
		if(t)a=max(a, find(max(t-k, 0), t-1));
		if(t<k)a=max(a, find(n+t-k, n-1));
		if(a==0)Left[0][kol[i]]=n;
		else Left[0][kol[i]]=(n-kol[n-a]+kol[i])%n;
		a=0;
		if(t<n-1)a=max(a, find( t+1, min(n-1, t+k)));
		if(t+k>=n)a=max(a, find(0, t+k-n));
		if(a==0)Right[0][kol[i]]=n;
		else Right[0][kol[i]]=(n+kol[n-a]-kol[i])%n;
		Set(kol[i], n-i);
		//cout<<kol[i]<<" "<<Left[0][kol[i]]<<" "<<Right[0][kol[i]]<<"\n";
	}
	for(int j=1; j<K; j++){
		for(int i=0; i<n; i++){
			Left[j][i]=Left[j-1][i]+Left[j-1][((i-Left[j-1][i])%n+n)%n];
			Right[j][i]=Right[j-1][i]+Right[j-1][(i+Right[j-1][i])%n];
			//cout<<j<<" "<<i<<" "<<Left[j][i]<<" "<<Right[j][i]<<"\n";
		}
	}
}
int compare_plants(int x, int y){
   	int a=1, b=0;
   	if(gdzie[x]>gdzie[y])swap(x, y), a=-1;
	int t=(n+x-y)%n, u=0;
	for(int i=K-1; i>=0; i--){
		if(u+Left[i][(n+x-u)%n]<=t){
			u+=Left[i][(n+x-u)%n];
		}
	}
	//cout<<x<<" "<<y<<" "<<u<<" "<<t<<"\n";
	int s=(n+x-u)%n;
	if(((n+s-y)%n<=k || (n+y-s)%n<=k) && gdzie[(n+x-u)%n]<=gdzie[y])b=1;
	t=(n+y-x)%n, u=0;
	for(int i=K-1; i>=0; i--){
		if(u+Right[i][(u+x)%n]<=t){
			u+=Right[i][(u+x)%n];
		}
	}
	s=(n+x+u)%n;
	if(((n+s-y)%n<=k || (n+y-s)%n<=k) && gdzie[(x+u)%n]<=gdzie[y])b=1;
   	return a*b;
}

• 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