oj.uz

Submission #303424

# Submission time Handle Problem Language Result Execution time Memory
303424 2020-09-20T09:58:11 Z Utaha Comparing Plants (IOI20_plants) C++14
44 / 100
 1212 ms 28764 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
#define REP(i,n) for(int i=0;i<(n);i++)
#define eb emplace_back
#define pb push_back
#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(),a.end()
const int INF = 0x3f3f3f3f;
int n,k;
//bool adj[maxn][maxn];

set<int> zero;
set<int> st;

vector<int> a;
vector<int> _a;
vector<int> b;

int seg[maxn*4]; // store the minimum
int tg[maxn*4];

void push(int i){
	seg[i*2]+=tg[i];
	tg[i*2]+=tg[i];
	seg[i*2+1]+=tg[i];
	tg[i*2+1]+=tg[i];
	tg[i]=0;
}

void mdf(int i,int l,int r,int ql,int qr, int delta){
	if(l>=qr||ql>=r) return;
	if(ql<=l&&r<=qr){
		seg[i]+=delta;
		tg[i]+=delta;
		return;
	}
	int mid=(l+r)/2;
	push(i);
	mdf(i*2,l,mid,ql,qr,delta);
	mdf(i*2+1,mid,r,ql,qr,delta);
	seg[i] = min(seg[i*2],seg[i*2+1]);
}

void reset(int i,int l,int r){
	seg[i]=tg[i]=0;
	if(l!=r-1){
		int mid=(l+r)/2;
		reset(i*2,l,mid);
		reset(i*2+1,mid,r);
	}
}

int get_idx(int i,int l,int r){
	if(l==r-1) return l;
	int mid=(l+r)/2;
	push(i);
	if(seg[i*2]==seg[i]) return get_idx(i*2,l,mid);
	else return get_idx(i*2+1,mid,r);
}

void add(int i){ // adding i to zero while maintaining st
	if(zero.count(i))return;
	// cout<<"adding: "<<i<<endl;

	auto it = zero.lower_bound(i);

	if(SZ(zero)==0){
		zero.insert(i);
	}
	else if(it==zero.end()){
		int pre = *prev(zero.end());
		if(i-pre>=k) st.insert(i);
	}
	else if(it==zero.begin()){
		if((*it) - i >=k){
			st.insert((*zero.begin()));
		}
	}
	else{
		int pre = *prev(it);
		int nxt = *it;

		if(nxt-pre>=k){
			st.erase(nxt);
		}

		if(i-pre>=k) st.insert(i);
		if(nxt - i >=k){
			st.insert(nxt);
		}
	}
	zero.insert(i);
}

void rm(int i){ // removing i to zero while maintaining st
	if(!zero.count(i)) return;
	// cout<<"removing: "<<i<<endl;
	zero.erase(i);
	auto it = zero.lower_bound(i);

	if(it==zero.end()){
		st.erase(i);
	}
	else if(it==zero.begin()){
		st.erase(*it);
	}
	else{
		int pre = *prev(it);
		int nxt = *it;

		if(i-pre>=k) st.erase(i);
		if(nxt - i >=k){
			st.erase(nxt);
		}

		if(nxt-pre>=k){
			st.insert(nxt);
		}

	}

}

void init(int _k, std::vector<int> _r) {
	k=_k;
	n = _r.size();

	{
		zero.clear();
		st.clear();
		vector<int> r = _r;
		REP(j,n){
			if(r[j]==0) zero.insert(j),zero.insert(j+n);
		}
		{
			int pre = -1;
			for(int i:zero){
				if(pre!=-1&&i-pre>=k){
					st.insert(i);
				}
				pre = i;
			}
		}

		REP(i,n){
			mdf(1,0,n,i,i+1,(r[i])?r[i]:INF);
		}

		REP(i,n){
			int tmp = *st.begin();
			tmp%=n;
			// cout<<"found: "<<tmp<<endl;
			a.pb(tmp);
			st.erase(tmp);
			st.erase(tmp+n);
			rm(tmp);
			rm(tmp+n);

			int l = (tmp-(k-1)+n)%n, r = tmp;
			if(l<r){
				mdf(1,0,n,l,r,-1);
			}
			else{
				mdf(1,0,n,l,n,-1);
				mdf(1,0,n,0,r,-1);
			}

			while(seg[1] == 0){
				int cur = get_idx(1,0,n);
				// cout<<"new: "<<cur<<endl;
				add(cur);
				add(cur+n);
				mdf(1,0,n,cur,cur+1,INF);
			}
			// cout<<"zero: ";
			// for(int j:zero) cout<<j<<' ';
			// cout<<'\n';
			// cout<<"st: ";
			// for(int j:st) cout<<j<<' ';
			// cout<<'\n';
		}

		// REP(i,n) cout<<a[i]<<" \n"[i==n-1];
		// cout<<endl;
	}

	{
		reset(1,0,n);
		zero.clear();
		st.clear();
		vector<int> r = _r;
		REP(i,n) r[i] = (k-1-r[i]);
		// REP(i,n) cout<<r[i]<<" \n"[i==n-1];
		REP(j,n){
			if(r[j]==0) zero.insert(j),zero.insert(j+n);
		}
		{
			int pre = -1;
			for(int i:zero){
				if(pre!=-1&&i-pre>=k){
					st.insert(i);
				}
				pre = i;
			}
		}

		REP(i,n){
			mdf(1,0,n,i,i+1,(r[i])?r[i]:INF);
		}

		REP(i,n){
			int tmp = *st.begin();
			tmp%=n;
			// cout<<"found: "<<tmp<<endl;
			b.pb(tmp);
			st.erase(tmp);
			st.erase(tmp+n);
			rm(tmp);
			rm(tmp+n);

			int l = (tmp-(k-1)+n)%n, r = tmp;
			if(l<r){
				mdf(1,0,n,l,r,-1);
			}
			else{
				mdf(1,0,n,l,n,-1);
				mdf(1,0,n,0,r,-1);
			}

			while(seg[1] == 0){
				int cur = get_idx(1,0,n);
				// cout<<"new: "<<cur<<endl;
				add(cur);
				add(cur+n);
				mdf(1,0,n,cur,cur+1,INF);
			}
			// cout<<"zero: ";
			// for(int j:zero) cout<<j<<' ';
			// cout<<'\n';
			// cout<<"st: ";
			// for(int j:st) cout<<j<<' ';
			// cout<<'\n';
		}

		// REP(i,n) cout<<b[i]<<" \n"[i==n-1];
	}

	// {
	// 	bool vis[maxn]={0};
	// 	for(int i:a){
	// 		for(int j=i+1;j<i+k;j++){
	// 			// cout<<i<<' '<<j<<endl;
	// 			int t = j%n;
	// 			if(!vis[t]){
	// 				adj[i][t]=1;
	// 			}
	// 		}
	// 		vis[i]=1;
	// 	}
	// }
	// {
	// 	bool vis[maxn]={0};
	// 	for(int i:b){
	// 		for(int j=i+1;j<i+k;j++){
	// 			int t = j%n;
	// 			if(!vis[t]){
	// 				adj[t][i]=1;
	// 			}
	// 		}
	// 		vis[i]=1;
	// 	}
	// }
	_a.resize(n);
	REP(i,n){
		_a[a[i]]=i;
	}
	// REP(i,n) REP(j,n) cout<<adj[i][j]<<" \n"[j==n-1];

	// REP(j,n) REP(i,n) REP(k,n){
	// 	if(adj[i][j]&&adj[j][k]) adj[i][k] = 1;
	// }

	return;
}


int compare_plants(int x, int y) {
	if(_a[x]<_a[y]) return 1;
	else if(_a[y]<_a[x]) return -1;
	else return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 87 ms 3524 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 116 ms 3452 KB Output is correct
11 Correct 106 ms 3520 KB Output is correct
12 Correct 84 ms 3704 KB Output is correct
13 Correct 87 ms 3448 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 87 ms 3524 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 116 ms 3452 KB Output is correct
11 Correct 106 ms 3520 KB Output is correct
12 Correct 84 ms 3704 KB Output is correct
13 Correct 87 ms 3448 KB Output is correct
14 Correct 166 ms 4316 KB Output is correct
15 Correct 1008 ms 11800 KB Output is correct
16 Correct 164 ms 4172 KB Output is correct
17 Correct 1028 ms 11760 KB Output is correct
18 Correct 1034 ms 19188 KB Output is correct
19 Correct 1049 ms 20488 KB Output is correct
20 Correct 940 ms 11908 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 81 ms 3256 KB Output is correct
4 Correct 902 ms 16508 KB Output is correct
5 Correct 1154 ms 13180 KB Output is correct
6 Correct 1212 ms 11964 KB Output is correct
7 Correct 1182 ms 11784 KB Output is correct
8 Correct 1085 ms 11968 KB Output is correct
9 Correct 1063 ms 14052 KB Output is correct
10 Correct 1177 ms 13248 KB Output is correct
11 Correct 803 ms 27964 KB Output is correct
12 Correct 872 ms 28764 KB Output is correct
13 Correct 966 ms 22856 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -