oj.uz

Submission #1063328

# Submission time Handle Problem Language Result Execution time Memory
1063328 2024-08-17T16:55:55 Z Itamar Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 32596 KB 
#include<vector>
#define vi vector<int>
using namespace std;
#include<queue>
#include <set>
const int siz = 2e5+2;
int ans[siz];
int N,K;
vi R;
int dis(int a, int b){ // oriented
	if(b > a)return b-a;
	return b-a+N;
}
queue<int> q;

struct node{
	int l,r,mid,minir,plus;
	node* sl,*sr;
	node(int li, int ri){
		l = li, r = ri, mid = (l+r)/2,plus=0;
		if(l<r){
			sl = new node(l,mid);
			sr = new node(mid+1,r);
			minir = min(sl->minir,sr->minir);
		}else{
			minir = R[l];
		}
	}
	void push(){
		if(l==r)return;
		sl->minir+=plus;
		sr->minir+=plus;
		sl->plus+=plus;
		sr->plus+=plus;
		plus=0;
	}
	void update(int a, int b, int p){
		push();
		if(r < a || l > b)return;
		if(a <= l && b >= r){
			minir+=p;
			plus+=p;
		}else{
			sl->update(a,b,p);
			sr->update(a,b,p);
			minir = min(sl->minir,sr->minir);
		}
	}
	int find(){
     	push();
		if(l==r){
			if(minir<=0){
				return l;
			}
			else return 1e9;
		}
		if(sl->minir<=0){
			
			return sl->find();
		}
		else if(sr->minir <=0)return sr->find();
		else return 1e9;
	}
};
set<int> s;
node* seg;
bool check(int i){
	auto it = s.find(i);
	if(it == s.end())return 0;
	auto it2 = it;
	int j;
	if(it2!=s.begin())j = *(--it2);
	else j =  *(s.rbegin());
	if(*it2 == i){
		q.push(i);
		return 1;
	}
	if(dis(*it2,i)>=K ){
		q.push(i);
		return 1;
	}
	else{
		return 0;
	}
}
void ins(int i){ // he now has r[i]=0
	//auto it = s.find(i);
	s.insert(i);
}
int mod(int i){
	return (i+N)%N;
}
void er(int i){ // i was considered as a maximum
	auto it = s.find(i);
	if(i>=K-1){
		seg->update(i-K+1,i,-1);
	}else{
		seg->update(0,i,-1);
		seg->update(mod(i-K+1),N-1,-1);
	}
	auto it1 = it, it2 = it;
	it2++;
	s.erase(i);if(s.empty())return;
	if(it2 == s.end())it2 = s.begin();
	check(*it2);
}
void init(int k, std::vector<int> r) {
	N = r.size(), K = k, R = r;
	 seg = new node(0,N-1);
	
	while(true){
		int f = seg->find();
		seg->update(f,f,1e9);
		if(f==1e9)break;
		ins(f);
	}
	for(int i : s)check(i);
	int ito = 1;
	vi vis(N);
	while(!q.empty()){

		int i = q.front();
		for(int j : s)if(check(j))i=j;
		q.pop();
		if(vis[i])continue;
		if(check(i)==0)continue;
		vis[i]=1;
		er(i);
		ans[i]=ito;
		ito++;
		vi vec;
		while(true){
		int f = seg->find();
			seg->update(f,f,1e9);
		if(f==1e9)break;
		ins(f);
		vec.push_back(f);
		}
		for(int f : vec)check(f);
	}
	/*for(int i = 0; i < N; i++){
		if(ans[i]==0){
			for(int j = 0; j < 2e9; j++){
				ans[i] = (ans[i]+1)%N;
			}
		}
	}*/
	int i =5;
	return;
}

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

Compilation message

plants.cpp: In function 'bool check(int)':
plants.cpp:71:6: warning: variable 'j' set but not used [-Wunused-but-set-variable]
   71 |  int j;
      |      ^
plants.cpp: In function 'void er(int)':
plants.cpp:101:7: warning: variable 'it1' set but not used [-Wunused-but-set-variable]
  101 |  auto it1 = it, it2 = it;
      |       ^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:148:6: warning: unused variable 'i' [-Wunused-variable]
  148 |  int i =5;
      |      ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 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 392 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 35 ms 5736 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 35 ms 5544 KB Output is correct
11 Correct 426 ms 5716 KB Output is correct
12 Correct 36 ms 5712 KB Output is correct
13 Correct 35 ms 5724 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 392 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 35 ms 5736 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 35 ms 5544 KB Output is correct
11 Correct 426 ms 5716 KB Output is correct
12 Correct 36 ms 5712 KB Output is correct
13 Correct 35 ms 5724 KB Output is correct
14 Correct 50 ms 7760 KB Output is correct
15 Correct 294 ms 30800 KB Output is correct
16 Correct 51 ms 7748 KB Output is correct
17 Correct 278 ms 30804 KB Output is correct
18 Execution timed out 4057 ms 32596 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 39 ms 5332 KB Output is correct
4 Execution timed out 4080 ms 30756 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -