oj.uz

Submission #1053988

# Submission time Handle Problem Language Result Execution time Memory
1053988 2024-08-12T02:41:44 Z pcc Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 161576 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[dp[i][j-1]][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[dp[i][j-1]][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 s = x,e = y;
	if(e<s)e += N;
	int ans = 0;
	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 13 ms 129880 KB Output is correct
2 Correct 13 ms 129812 KB Output is correct
3 Correct 14 ms 129880 KB Output is correct
4 Correct 12 ms 129844 KB Output is correct
5 Incorrect 13 ms 129876 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 13 ms 129628 KB Output is correct
2 Correct 12 ms 129884 KB Output is correct
3 Correct 12 ms 129880 KB Output is correct
4 Correct 12 ms 129884 KB Output is correct
5 Correct 14 ms 129820 KB Output is correct
6 Correct 31 ms 129884 KB Output is correct
7 Correct 137 ms 133200 KB Output is correct
8 Correct 14 ms 129880 KB Output is correct
9 Correct 30 ms 129996 KB Output is correct
10 Correct 134 ms 133200 KB Output is correct
11 Correct 161 ms 133460 KB Output is correct
12 Correct 145 ms 133200 KB Output is correct
13 Correct 127 ms 133192 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 129628 KB Output is correct
2 Correct 12 ms 129884 KB Output is correct
3 Correct 12 ms 129880 KB Output is correct
4 Correct 12 ms 129884 KB Output is correct
5 Correct 14 ms 129820 KB Output is correct
6 Correct 31 ms 129884 KB Output is correct
7 Correct 137 ms 133200 KB Output is correct
8 Correct 14 ms 129880 KB Output is correct
9 Correct 30 ms 129996 KB Output is correct
10 Correct 134 ms 133200 KB Output is correct
11 Correct 161 ms 133460 KB Output is correct
12 Correct 145 ms 133200 KB Output is correct
13 Correct 127 ms 133192 KB Output is correct
14 Correct 465 ms 135160 KB Output is correct
15 Execution timed out 4075 ms 161576 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 129880 KB Output is correct
2 Correct 12 ms 129628 KB Output is correct
3 Incorrect 104 ms 132752 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 129884 KB Output is correct
2 Correct 11 ms 129884 KB Output is correct
3 Correct 12 ms 129872 KB Output is correct
4 Incorrect 12 ms 129884 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 129880 KB Output is correct
2 Correct 13 ms 129812 KB Output is correct
3 Correct 14 ms 129880 KB Output is correct
4 Correct 12 ms 129844 KB Output is correct
5 Incorrect 13 ms 129876 KB Output isn't correct
6 Halted 0 ms 0 KB -