oj.uz

Submission #303426

# Submission time Handle Problem Language Result Execution time Memory
303426 2020-09-20T10:00:44 Z Utaha Comparing Plants (IOI20_plants) C++14
59 / 100
 1235 ms 28924 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;

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

vector<int> a;
vector<int> _a;
vector<int> b;
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;
	}
	_b.resize(n);
	REP(i,n){
		_b[b[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]&&_b[x]>_b[y]) return 1;
	else if(_a[y]<_a[x]&&_b[y]>_b[x]) return -1;
	else return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 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 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 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 88 ms 3448 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 87 ms 3448 KB Output is correct
11 Correct 85 ms 3524 KB Output is correct
12 Correct 84 ms 3704 KB Output is correct
13 Correct 88 ms 3448 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 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 88 ms 3448 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 87 ms 3448 KB Output is correct
11 Correct 85 ms 3524 KB Output is correct
12 Correct 84 ms 3704 KB Output is correct
13 Correct 88 ms 3448 KB Output is correct
14 Correct 150 ms 4308 KB Output is correct
15 Correct 1036 ms 12132 KB Output is correct
16 Correct 152 ms 4192 KB Output is correct
17 Correct 1026 ms 11868 KB Output is correct
18 Correct 1031 ms 19188 KB Output is correct
19 Correct 1028 ms 20576 KB Output is correct
20 Correct 907 ms 11996 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 1 ms 384 KB Output is correct
3 Correct 78 ms 3320 KB Output is correct
4 Correct 905 ms 16556 KB Output is correct
5 Correct 1078 ms 13152 KB Output is correct
6 Correct 1172 ms 12000 KB Output is correct
7 Correct 1232 ms 11924 KB Output is correct
8 Correct 1046 ms 11904 KB Output is correct
9 Correct 1064 ms 14096 KB Output is correct
10 Correct 1120 ms 13412 KB Output is correct
11 Correct 793 ms 28140 KB Output is correct
12 Correct 851 ms 28924 KB Output is correct
13 Correct 968 ms 22776 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 1149 ms 12068 KB Output is correct
7 Correct 1232 ms 12144 KB Output is correct
8 Correct 1235 ms 11740 KB Output is correct
9 Correct 1038 ms 11868 KB Output is correct
10 Correct 1043 ms 13924 KB Output is correct
11 Correct 1057 ms 11892 KB Output is correct
12 Correct 871 ms 16484 KB Output is correct
13 Correct 1060 ms 13320 KB Output is correct
14 Correct 1167 ms 12252 KB Output is correct
15 Correct 1194 ms 12008 KB Output is correct
16 Correct 1212 ms 14876 KB Output is correct
17 Correct 1066 ms 11968 KB Output is correct

Subtask #7
0 / 25.0

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