oj.uz

Submission #1063369

# Submission time Handle Problem Language Result Execution time Memory
1063369 2024-08-17T17:24:58 Z Itamar Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 326640 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{
		q.push(i);
		return 0;
	}
}
void ins(int i){ // he now has r[i]=0
	//auto it = s.find(i);
	s.insert(i);
	q.push(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++;
	it1--;
	
	s.erase(i);if(s.empty())return;
	if(it1 == s.end())it1 = s.begin();
	q.push(*it1);
	if(it2 == s.end())it2 = s.begin();
	q.push(*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)q.push(i);
	int ito = 1;
	vi vis(N);
	while(ito<=N){

		int i = q.front();
		for(int j : s)if(check(j))i=j;
		q.pop();
		
		if(vis[i])continue;
		q.push(i);
		if(check(i)==0)continue;
		vis[i]=1;
		er(i);
		ans[i]=ito;
		ito++;
		while(true){
		int f = seg->find();
			seg->update(f,f,1e9);
		if(f==1e9)break;
		ins(f);
		q.push(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 init(int, std::vector<int>)':
plants.cpp:155:6: warning: unused variable 'i' [-Wunused-variable]
  155 |  int i =5;
      |      ^

Subtask #1
0 / 5.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 0 ms 344 KB Output is correct
4 Incorrect 1 ms 600 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 424 KB Output is correct
7 Correct 38 ms 5744 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 35 ms 5740 KB Output is correct
11 Correct 410 ms 44136 KB Output is correct
12 Correct 34 ms 5716 KB Output is correct
13 Correct 35 ms 5716 KB Output is correct

Subtask #3
0 / 13.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 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 424 KB Output is correct
7 Correct 38 ms 5744 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 35 ms 5740 KB Output is correct
11 Correct 410 ms 44136 KB Output is correct
12 Correct 34 ms 5716 KB Output is correct
13 Correct 35 ms 5716 KB Output is correct
14 Correct 57 ms 8060 KB Output is correct
15 Correct 317 ms 33616 KB Output is correct
16 Correct 53 ms 8304 KB Output is correct
17 Correct 295 ms 33980 KB Output is correct
18 Execution timed out 4040 ms 315752 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 1 ms 348 KB Output is correct
3 Correct 45 ms 6728 KB Output is correct
4 Execution timed out 4088 ms 326640 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 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 #7
0 / 25.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 0 ms 344 KB Output is correct
4 Incorrect 1 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -