oj.uz

답안 #1053992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1053992 2024-08-12T02:58:00 Z pcc 식물 비교 (IOI20_plants) C++17
25 / 100
 4000 ms 165884 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[N*2-1-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[N*2-1-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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 129628 KB Output is correct
2 Correct 11 ms 129628 KB Output is correct
3 Correct 11 ms 129744 KB Output is correct
4 Correct 11 ms 129628 KB Output is correct
5 Correct 11 ms 129720 KB Output is correct
6 Correct 39 ms 133656 KB Output is correct
7 Correct 170 ms 137368 KB Output is correct
8 Correct 484 ms 164180 KB Output is correct
9 Correct 557 ms 163412 KB Output is correct
10 Correct 1250 ms 163924 KB Output is correct
11 Execution timed out 4046 ms 165884 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 129628 KB Output is correct
2 Correct 12 ms 129636 KB Output is correct
3 Correct 11 ms 129628 KB Output is correct
4 Correct 12 ms 129628 KB Output is correct
5 Correct 11 ms 129784 KB Output is correct
6 Correct 14 ms 129856 KB Output is correct
7 Correct 49 ms 132952 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 132936 KB Output is correct
11 Correct 506 ms 133204 KB Output is correct
12 Correct 501 ms 132944 KB Output is correct
13 Correct 48 ms 132948 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 129628 KB Output is correct
2 Correct 12 ms 129636 KB Output is correct
3 Correct 11 ms 129628 KB Output is correct
4 Correct 12 ms 129628 KB Output is correct
5 Correct 11 ms 129784 KB Output is correct
6 Correct 14 ms 129856 KB Output is correct
7 Correct 49 ms 132952 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 132936 KB Output is correct
11 Correct 506 ms 133204 KB Output is correct
12 Correct 501 ms 132944 KB Output is correct
13 Correct 48 ms 132948 KB Output is correct
14 Correct 95 ms 134136 KB Output is correct
15 Correct 776 ms 148356 KB Output is correct
16 Correct 100 ms 134228 KB Output is correct
17 Correct 778 ms 148380 KB Output is correct
18 Execution timed out 4045 ms 161360 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 129624 KB Output is correct
2 Correct 11 ms 129628 KB Output is correct
3 Correct 698 ms 132692 KB Output is correct
4 Execution timed out 4046 ms 154960 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 129828 KB Output is correct
2 Correct 11 ms 129788 KB Output is correct
3 Correct 11 ms 129628 KB Output is correct
4 Correct 11 ms 129780 KB Output is correct
5 Correct 12 ms 129840 KB Output is correct
6 Correct 13 ms 129892 KB Output is correct
7 Correct 21 ms 130652 KB Output is correct
8 Correct 19 ms 130732 KB Output is correct
9 Correct 30 ms 130648 KB Output is correct
10 Correct 20 ms 130652 KB Output is correct
11 Correct 22 ms 130632 KB Output is correct
12 Correct 23 ms 130648 KB Output is correct
13 Correct 18 ms 130652 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 129880 KB Output is correct
2 Correct 11 ms 129716 KB Output is correct
3 Correct 11 ms 129628 KB Output is correct
4 Correct 11 ms 129884 KB Output is correct
5 Correct 13 ms 129884 KB Output is correct
6 Correct 597 ms 145288 KB Output is correct
7 Correct 1097 ms 145232 KB Output is correct
8 Correct 748 ms 145492 KB Output is correct
9 Correct 765 ms 149656 KB Output is correct
10 Execution timed out 4022 ms 153936 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 129628 KB Output is correct
2 Correct 11 ms 129628 KB Output is correct
3 Correct 11 ms 129744 KB Output is correct
4 Correct 11 ms 129628 KB Output is correct
5 Correct 11 ms 129720 KB Output is correct
6 Correct 39 ms 133656 KB Output is correct
7 Correct 170 ms 137368 KB Output is correct
8 Correct 484 ms 164180 KB Output is correct
9 Correct 557 ms 163412 KB Output is correct
10 Correct 1250 ms 163924 KB Output is correct
11 Execution timed out 4046 ms 165884 KB Time limit exceeded
12 Halted 0 ms 0 KB -