oj.uz

Submission #1053991

# Submission time Handle Problem Language Result Execution time Memory
1053991 2024-08-12T02:53:39 Z pcc Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 161364 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int B = 20;
const int mxn = 4e5+10;

int arr[mxn];
int N;
int K;
int perm[mxn];
int dp[mxn];
set<int> st;
set<pii> rng;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	pii seg[mxn*4];
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].sc += v;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		seg[now].fs = min(seg[ls].fs+seg[ls].sc,seg[rs].fs+seg[rs].sc);
		return;
	}
	int get_mn(int now,int l,int r){
		if(l == r){
			return l;
		}
		if(seg[ls].fs+seg[ls].sc<seg[rs].fs+seg[rs].sc)return get_mn(ls,l,mid);
		else return get_mn(rs,mid+1,r);
	}
#undef ls
#undef rs
#undef mid
}seg;


void add(int p){
	int nxt = *st.upper_bound(p);
	int pre = *(--st.upper_bound(p));
	rng.erase(pii(nxt-pre,nxt));
	rng.insert(pii(nxt-p,nxt));
	rng.insert(pii(p-pre,p));
	st.insert(p);
	return;
}

void del(int p){
	auto it = st.find(p);
	int pre = *prev(it),nxt = *next(it);
	rng.erase(pii(p-pre,p));
	rng.erase(pii(nxt-p,nxt));
	rng.insert(pii(nxt-pre,nxt));
	st.erase(p);
	return;
}

struct DB{
	int dp[mxn][B];
	DB(){
		memset(dp,-1,sizeof(dp));
	}
	void build(int s,int e){
		if(e<s){
			for(int i = s;i>=e;i--){
				for(int j = 1;j<B;j++){
					int pre = dp[i][j-1];
					if(pre == -1)continue;
					dp[i][j] = dp[pre][j-1];
				}
			}
		}
		else{
			for(int i = s;i<=e;i++){
				for(int j = 1;j<B;j++){
					int pre = dp[i][j-1];
					if(pre == -1)continue;
					dp[i][j] = dp[pre][j-1];
				}
			}
		}
	}
};

DB lmx,rmx,lmn,rmn;

void calc(int id){
	auto it = rng.rbegin();
	if(it->sc >= N*2)it++;
	auto pos = it->sc;
	pos %= N;
	//cerr<<id<<":"<<pos<<','<<it->fs<<endl;
	assert(it->fs>=K);
	del(pos);
	del(pos+N);
	perm[pos] = id;
	seg.modify(0,0,N*2-1,pos+N-K+1,pos+N,-1);
	seg.modify(0,0,N*2-1,max(pos-K+1,0),pos,-1);
	if(pos-K+1<0)seg.modify(0,0,N*2-1,N*2-1+(pos-K+1)+1,N*2-1,-1);
	while(seg.seg[0].fs+seg.seg[0].sc == 0){
		int p = seg.get_mn(0,0,N*2-1);
		p %= N;
		add(p);
		seg.modify(0,0,N*2-1,p,p,mxn*4);
		add(p+N);
		seg.modify(0,0,N*2-1,p+N,p+N,mxn*4);
	}
	return;
}

void init(int k, std::vector<int> r) {
	K = k;
	N = r.size();
	for(int i = 0;i<N;i++)arr[i] = arr[i+N] = r[i];
	st.insert(-1);
	st.insert(N*2);
	rng.insert(pii(N*2+1,N*2));
	for(int i = 0;i<N*2;i++){
		if(!arr[i]){
			add(i);
		}
		if(arr[i])seg.modify(0,0,N*2-1,i,i,arr[i]);
		else seg.modify(0,0,N*2-1,i,i,mxn*4);
	}
	//cerr<<"INIT!: "<<rng.rbegin()->fs<<endl;
	//for(auto &i:rng)cerr<<i.fs<<','<<i.sc<<endl;
	for(int i = N-1;i>=0;i--)calc(i);
	//for(int i = 0;i<N;i++)cerr<<perm[i]<<',';cerr<<endl;
	for(int i = N;i<N*2;i++)perm[i] = perm[i-N];
	set<pii> st;
	for(int i = 0;i<K-1;i++){
		auto it = st.lower_bound(pii(perm[i],-1));
		if(it != st.end())lmx.dp[i][0] = it->sc;
		if(it != st.begin()){
			it--;
			lmn.dp[i][0] = it->sc;
		}
		st.insert(pii(perm[i],i));
	}
	for(int i = K-1;i<N*2;i++){
		auto it = st.lower_bound(pii(perm[i],-1));
		if(it != st.end())lmx.dp[i][0] = it->sc;
		if(it != st.begin()){
			it--;
			lmn.dp[i][0] = it->sc;
		}
		st.erase(pii(perm[i-K+1],i-K+1));
		st.insert(pii(perm[i],i));
	}
	st.clear();
	for(int i = 0;i<K-1;i++){
		auto it = st.lower_bound(pii(perm[N*2-1-i],-1));
		if(it != st.end())rmx.dp[i][0] = it->sc;
		if(it != st.begin()){
			it--;
			rmn.dp[N*2-1-i][0] = it->sc;
		}
		st.insert(pii(perm[N*2-1-i],N*2-1-i));
	}
	for(int i = K-1;i<N*2;i++){
		auto it = st.lower_bound(pii(perm[N*2-1-i],-1));
		if(it != st.end())rmx.dp[i][0] = it->sc;
		if(it != st.begin()){
			it--;
			rmn.dp[N*2-1-i][0] = it->sc;
		}
		st.erase(pii(perm[N*2-1-i+K-1],N*2-1-i+K-1));
		st.insert(pii(perm[N*2-1-i],N*2-1-i));
	}
	rmn.build(N*2-1,0);
	rmx.build(N*2-1,0);
	lmn.build(0,N*2-1);
	lmx.build(0,N*2-1);
	/*
	cerr<<"PERM: "<<endl;for(int i = 0;i<N*2;i++)cerr<<perm[i]<<' ';cerr<<endl;
	cerr<<"LMX: "<<endl;for(int i = 0;i<N*2;i++)cerr<<lmx.dp[i][0]<<' ';cerr<<endl;
	cerr<<"LMN: "<<endl;for(int i = 0;i<N*2;i++)cerr<<lmn.dp[i][0]<<' ';cerr<<endl;
	cerr<<"RMX: "<<endl;for(int i = 0;i<N*2;i++)cerr<<rmx.dp[i][0]<<' ';cerr<<endl;
	cerr<<"RMN: "<<endl;for(int i = 0;i<N*2;i++)cerr<<rmn.dp[i][0]<<' ';cerr<<endl;
	*/
	return;
}

int compare_plants(int x, int y) {

	int ans = 0;

	int s = x,e = y;
	if(e<s)e += N;
	while(e-s>=K){
		if(rmx.dp[s][0] != -1&&rmx.dp[s][0]<e)s = rmx.dp[s][0];
		else break;
	}
	if(e-s<K&&perm[e]>perm[s])ans = -1;
	s = x,e = y;
	if(e>s)s += N;
	while(s-e>=K){
		if(lmx.dp[s][0] != -1&&lmx.dp[s][0]>e)s = lmx.dp[s][0];
		else break;
	}
	if(s-e<K&&perm[e]>perm[s])ans = -1;

	s = x,e = y;
	if(e<s)e += N;
	while(e-s>=K){
		if(rmn.dp[s][0] != -1&&rmn.dp[s][0]<e)s = rmn.dp[s][0];
		else break;
	}
	if(e-s<K&&perm[e]<perm[s])ans = 1;
	s = x,e = y;
	if(e>s)s += N;
	while(s-e>=K){
		if(lmn.dp[s][0] != -1&&lmn.dp[s][0]>e)s = lmn.dp[s][0];
		else break;
	}
	if(s-e<K&&perm[e]<perm[s])ans = 1;
	/*
	for(int i = B-1;i>=0;i--){
		if(e-s<K)break;
		if(rmx.dp[s][i] != -1&&rmx.dp[s][i]<e)s = rmx.dp[s][i];
	}
	if(e-s<K&&perm[e]>perm[s])ans = -1;
	s = x,e = y;
	if(e>s)s += N;
	for(int i = B-1;i>=0;i--){
		if(s-e<K)break;
		if(lmx.dp[s][i] != -1&&lmx.dp[s][i]>e)s = lmx.dp[s][i];
	}
	if(s-e<K&&perm[e]>perm[s])ans = -1;

	s = x,e = y;
	if(e<s)e += N;
	for(int i = B-1;i>=0;i--){
		if(e-s<K)break;
		if(rmn.dp[s][i] != -1&&rmn.dp[s][i]<e)s = rmn.dp[s][i];
	}
	if(e-s<K&&perm[e]<perm[s])ans = 1;
	s = x,e = y;
	if(e>s)s += N;
	for(int i = B-1;i>=0;i--){
		if(s-e<K)break;
		if(lmn.dp[s][i] != -1&&lmn.dp[s][i]>e)s = lmn.dp[s][i];
	}
	if(s-e<K&&perm[e]<perm[s])ans = 1;
	*/
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 129628 KB Output is correct
2 Correct 11 ms 129628 KB Output is correct
3 Correct 12 ms 129880 KB Output is correct
4 Correct 12 ms 129628 KB Output is correct
5 Incorrect 12 ms 129840 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 129848 KB Output is correct
2 Correct 12 ms 129884 KB Output is correct
3 Correct 11 ms 129628 KB Output is correct
4 Correct 11 ms 129624 KB Output is correct
5 Correct 12 ms 129880 KB Output is correct
6 Correct 13 ms 129884 KB Output is correct
7 Correct 49 ms 133016 KB Output is correct
8 Correct 12 ms 129884 KB Output is correct
9 Correct 14 ms 129884 KB Output is correct
10 Correct 49 ms 132880 KB Output is correct
11 Correct 509 ms 133276 KB Output is correct
12 Correct 407 ms 133200 KB Output is correct
13 Correct 48 ms 132944 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 129848 KB Output is correct
2 Correct 12 ms 129884 KB Output is correct
3 Correct 11 ms 129628 KB Output is correct
4 Correct 11 ms 129624 KB Output is correct
5 Correct 12 ms 129880 KB Output is correct
6 Correct 13 ms 129884 KB Output is correct
7 Correct 49 ms 133016 KB Output is correct
8 Correct 12 ms 129884 KB Output is correct
9 Correct 14 ms 129884 KB Output is correct
10 Correct 49 ms 132880 KB Output is correct
11 Correct 509 ms 133276 KB Output is correct
12 Correct 407 ms 133200 KB Output is correct
13 Correct 48 ms 132944 KB Output is correct
14 Correct 95 ms 134200 KB Output is correct
15 Correct 769 ms 148264 KB Output is correct
16 Correct 97 ms 134228 KB Output is correct
17 Correct 791 ms 148312 KB Output is correct
18 Execution timed out 4069 ms 161364 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 129884 KB Output is correct
2 Correct 12 ms 129624 KB Output is correct
3 Incorrect 583 ms 132652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 129624 KB Output is correct
2 Correct 12 ms 129624 KB Output is correct
3 Correct 12 ms 129628 KB Output is correct
4 Incorrect 11 ms 129640 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 129624 KB Output is correct
2 Correct 11 ms 129748 KB Output is correct
3 Correct 11 ms 129628 KB Output is correct
4 Correct 12 ms 129628 KB Output is correct
5 Incorrect 15 ms 129900 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 129628 KB Output is correct
2 Correct 11 ms 129628 KB Output is correct
3 Correct 12 ms 129880 KB Output is correct
4 Correct 12 ms 129628 KB Output is correct
5 Incorrect 12 ms 129840 KB Output isn't correct
6 Halted 0 ms 0 KB -