oj.uz

Submission #300407

# Submission time Handle Problem Language Result Execution time Memory
300407 2020-09-17T06:53:54 Z kshitij_sodani Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 14584 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>aa or r<bb){
		return ;
	}
	if(aa<=l and r<=bb){
		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);
		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 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);
		}
		if(tree[no*2+1].a<tree[no*2+2].a){
			tree[no]=tree[no*2+1];
		}
		else{
			tree[no]=tree[no*2+2];
		}
	}
}

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);
			}
		}

		ind=*(cur2.begin());
		ans[ind]=i;


		//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;
			}
		}*/
		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;
			
			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 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 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 10 ms 384 KB Output is correct
7 Correct 240 ms 3492 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 9 ms 384 KB Output is correct
10 Correct 238 ms 3448 KB Output is correct
11 Correct 704 ms 3832 KB Output is correct
12 Correct 173 ms 3576 KB Output is correct
13 Correct 293 ms 3576 KB Output is correct

Subtask #3
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 10 ms 384 KB Output is correct
7 Correct 240 ms 3492 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 9 ms 384 KB Output is correct
10 Correct 238 ms 3448 KB Output is correct
11 Correct 704 ms 3832 KB Output is correct
12 Correct 173 ms 3576 KB Output is correct
13 Correct 293 ms 3576 KB Output is correct
14 Correct 1802 ms 4344 KB Output is correct
15 Execution timed out 4008 ms 10232 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 96 ms 3320 KB Output is correct
4 Execution timed out 4038 ms 14584 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 Incorrect 1 ms 512 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 1 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 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -