oj.uz

Submission #300441

# Submission time Handle Problem Language Result Execution time Memory
300441 2020-09-17T07:17:40 Z kshitij_sodani Comparing Plants (IOI20_plants) C++14
44 / 100
 551 ms 21368 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back

typedef long long llo;
#include "plants.h"
vector<int> it;
int n;

int k;
pair<int,int> tree[800001];
int lazy[800001];
void build(int no,int l,int r){
	if(l==r){
		tree[no]={it[l],l};
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		if(tree[no*2+1].a<tree[no*2+2].a){
			tree[no]=tree[no*2+1];
		}
		else{
			tree[no]=tree[no*2+2];
		}
	}
}
void update(int no,int l,int r,int aa,int bb){
	tree[no].a+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
	if(l>bb or r<aa){
		return ;
	}
	if(aa<=l and r<=bb){
	//	cout<<l<<"<"<<r<<endl;
		tree[no].a-=1;
		if(l<r){
			lazy[no*2+1]-=1;
			lazy[no*2+2]-=1;
		}
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb);
		update(no*2+2,mid+1,r,aa,bb);
		//	push(no*2+1);
		//push(no*2+2);
		if(tree[no*2+1].a<tree[no*2+2].a){
			tree[no]=tree[no*2+1];
		}
		else{
			tree[no]=tree[no*2+2];
		}
	}
}
void push(int no,int l,int r){
	tree[no].a+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
}
void update2(int no,int l,int r,int i){
	tree[no].a+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;

	if(l==r){
		tree[no]={1e9,-1};
	}
	else{
		int mid=(l+r)/2;
		if(i<=mid){
			update2(no*2+1,l,mid,i);
		}
		else{
			update2(no*2+2,mid+1,r,i);
		}
		push(no*2+1,l,mid);
		push(no*2+2,mid+1,r);
		if(tree[no*2+1].a<tree[no*2+2].a){
			tree[no]=tree[no*2+1];
		}
		else{
			tree[no]=tree[no*2+2];
		}
	}
	//cout<<l<<":"<<r<<":"<<tree[no].a<<endl;
}

int tree2[200001];
void u(int i,int j){
	while(i<200001){
		tree2[i]+=j;
		i+=(i&-i);
	}
}
int ss(int i){
	int su=0;
	while(i>0){
		su+=tree2[i];
		i-=(i&-i);
	}
	return su;
}
int ans[200001];
set<int> cur;

bool check(int j){
	if(cur.size()==1){
		return true;
	}
	auto jj=cur.find(j);
	int dis;
	if(jj==cur.begin()){
		jj=cur.end();
		jj--;
		dis=j+n-*jj;
	}
	else{
		jj--;
		dis=j-*jj;
	}
	if(dis>k-1){
		return true;
	}
	return false;

}
void init(int kk,vector<int> r){
	n=r.size();
	k=kk;
	it=r;
	
	build(0,0,n-1);
	set<int> cur2;
	for(int i=0;i<n;i++){
		if(it[i]==0){
			cur.insert(i);
			update2(0,0,n-1,i);
		}
	}
	for(auto j:cur){
		if(check(j)){
			cur2.insert(j);
		}
	}
	for(int i=0;i<n;i++){
		int ind=-1;
		/*cur2.clear();
		for(auto j:cur){
			if(check(j)){
				cur2.insert(j);
			}
		}*/
		/*for(auto j:cur){
			cout<<j<<",,";
		}
		cout<<endl;
*/
		ind=*(cur2.begin());
		ans[ind]=i;
	//	cout<<ind<<":"<<i<<endl;

		//int cot=ind;
		cur2.erase(ind);
		cur.erase(ind);
		if(cur.size()){
			auto j=cur.upper_bound(ind);
			if(j!=cur.end()){
				if(check(*j)){
					cur2.insert(*j);
				}
			}
			else{
				j=cur.begin();
				if(check(*j)){
					cur2.insert(*j);
				}
			}
		}
		//cout<<ind<<endl;

		if(ind>=k-1){
			update(0,0,n-1,ind-k+1,ind-1);
		}
		else{
			if(ind){
				update(0,0,n-1,0,ind-1);
			}

			int xx=(ind-k+1+n)%n;
			update(0,0,n-1,xx,n-1);
		}
		/*int cot=ind;
		for(int jj=0;jj<k-1;jj++){
			cot=(cot-1+n)%n;
			it[cot]-=1;
			if(it[cot]==0){
				cur.insert(cot);
				if(cur.size()>1){
					auto j=cur.upper_bound(cot);
					if(j==cur.end()){
						j=cur.begin();
						cur2.erase(*j);
						if(check(*j)){
							cur2.insert(*j);
						}
					}
					else{
						cur2.erase(*j);
						if(check(*j)){
							cur2.insert(*j);
						}	
					}
				}
				//cout<<tree[0].b<<endl;
				//cur.insert(cot);
				if(check(cot)){
					cur2.insert(tree[0].b);
				}
				//update2(0,0,n-1,tree[0].b);
			}
		}
		continue;
		*/
		/*if(tree[0].a<0){
			while(true){
				continue;
			}
		}*/
		//cout<<tree[0].a<<"//"<<tree[0].b<<endl;
		while(tree[0].a==0){
			cur.insert(tree[0].b);

			if(cur.size()>1){
				auto j=cur.upper_bound(tree[0].b);
				if(j==cur.end()){
					j=cur.begin();
					cur2.erase(*j);
					if(check(*j)){
						cur2.insert(*j);
					}
				}
				else{
					cur2.erase(*j);
					if(check(*j)){
						cur2.insert(*j);
					}	
				}
			}
			//cout<<tree[0].b<<endl;
			//cout<<tree[0].b<<endl;
			if(check(tree[0].b)){
				cur2.insert(tree[0].b);
			}
			update2(0,0,n-1,tree[0].b);
		}

	}




	return;
}

int compare_plants(int x, int y) {
/*	x=dis[x];
	y=dis[y];*/
	if(ans[x]<ans[y]){
		return 1;
	}
	else{
		return -1;
	}
	return 0;


	if(y-x<k){
		if(it[x]==0){
			return 1;
		}
		else if(it[x]==k-1){
			return -1;
		}
	}
	else{
		if(it[y]==0){
			return -1;
		}
		else if(it[y]==k-1){
			return 1;
		}
	}


	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 512 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 1 ms 384 KB Output is correct
3 Correct 1 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 3 ms 384 KB Output is correct
7 Correct 92 ms 3576 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 79 ms 3448 KB Output is correct
11 Correct 78 ms 3448 KB Output is correct
12 Correct 77 ms 3580 KB Output is correct
13 Correct 82 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 1 ms 384 KB Output is correct
3 Correct 1 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 3 ms 384 KB Output is correct
7 Correct 92 ms 3576 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 79 ms 3448 KB Output is correct
11 Correct 78 ms 3448 KB Output is correct
12 Correct 77 ms 3580 KB Output is correct
13 Correct 82 ms 3448 KB Output is correct
14 Correct 132 ms 4344 KB Output is correct
15 Correct 539 ms 12048 KB Output is correct
16 Correct 111 ms 4348 KB Output is correct
17 Correct 549 ms 12024 KB Output is correct
18 Correct 489 ms 16792 KB Output is correct
19 Correct 346 ms 12056 KB Output is correct
20 Correct 490 ms 11964 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 77 ms 3320 KB Output is correct
4 Correct 375 ms 15152 KB Output is correct
5 Correct 421 ms 12868 KB Output is correct
6 Correct 512 ms 12112 KB Output is correct
7 Correct 551 ms 12152 KB Output is correct
8 Correct 544 ms 11960 KB Output is correct
9 Correct 428 ms 14264 KB Output is correct
10 Correct 406 ms 12664 KB Output is correct
11 Correct 370 ms 21368 KB Output is correct
12 Correct 362 ms 12004 KB Output is correct
13 Correct 450 ms 18552 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.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 Incorrect 0 ms 288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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