oj.uz

답안 #1063358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063358 2024-08-17T17:14:59 Z Itamar 식물 비교 (IOI20_plants) C++14
14 / 100
 4000 ms 330116 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(!q.empty()){

		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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 36 ms 5600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 36 ms 5608 KB Output is correct
11 Correct 435 ms 43604 KB Output is correct
12 Correct 33 ms 5712 KB Output is correct
13 Correct 36 ms 5716 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 36 ms 5600 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 36 ms 5608 KB Output is correct
11 Correct 435 ms 43604 KB Output is correct
12 Correct 33 ms 5712 KB Output is correct
13 Correct 36 ms 5716 KB Output is correct
14 Correct 51 ms 8272 KB Output is correct
15 Correct 289 ms 33616 KB Output is correct
16 Correct 54 ms 8084 KB Output is correct
17 Correct 286 ms 34152 KB Output is correct
18 Execution timed out 4080 ms 319144 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 43 ms 6776 KB Output is correct
4 Execution timed out 4072 ms 330116 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 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 #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 360 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

# 결과 실행 시간 메모리 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 -