oj.uz

Submission #400306

# Submission time Handle Problem Language Result Execution time Memory
400306 2021-05-07T20:28:53 Z faresbasbs Comparing Plants (IOI20_plants) C++14
0 / 100
 65 ms 4840 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

struct node{
	int val,lazy;
};

int n,t,k,cnt,val[200001];
vector<node> segment;

void push(int curr){
	for(int i = 2*curr ; i <= 2*curr+1 ; i += 1){
		segment[i].lazy += segment[curr].lazy , segment[i].val += segment[curr].lazy;
	}
	segment[curr].lazy = 0;
}

void pull(int curr){
	segment[curr].val = min(segment[2*curr].val,segment[2*curr+1].val);
}

void upd(int a , int b , int v , int curr , int l , int r){
	if(b < l || a > r){
		return ;
	}
	if(a <= l && b >= r){
		segment[curr].val = v , segment[curr].lazy = 0;
		return ;
	}
	int mid = (l+r)/2;
	push(curr);
	upd(a,b,v,2*curr,l,mid),upd(a,b,v,2*curr+1,mid+1,r);
	pull(curr);
}

void rupd(int a , int b , int curr , int l , int r){
	if(b < l || a > r){
		return ;
	}
	if(a <= l && b >= r){
		segment[curr].lazy -= 1 , segment[curr].val -= 1;
		return ;
	}
	int mid = (l+r)/2;
	push(curr);
	rupd(a,b,2*curr,l,mid),rupd(a,b,2*curr+1,mid+1,r);
	pull(curr);
}

void u(int pos){
	val[pos] = cnt++;
	upd(pos,pos,1000000000,1,1,t);
	if(pos > 1){
		if(pos >= k){
			rupd(pos-k+1,pos-1,1,1,t);
		}else{
			int num = k-pos;
			rupd(1,pos-1,1,1,t),rupd(n-num,n,1,1,t);
		}
	}else{
		rupd(n-k+2,n,1,1,t);
	}
	// for(int i = 1 ; i < 2*t ; i += 1){
	// 	if(i < t){
	// 		push(i);
	// 	}
	// 	cout << segment[i].val << " ";
	// }cout << endl;
}

int fnd2(int a , int b , int curr , int l , int r){
	if(b < l || a > r){
		return -1;
	}
	if(a <= l && b >= r){
		// cout << cnt << " " << curr << " " << segment[curr].val << endl;
		if(segment[curr].val != 0){
			return -1;
		}
		while(curr < t){
			push(curr);
			if(segment[2*curr].val == 0){
				curr = 2*curr;
			}else{
				curr = 2*curr+1;
			}
		}
		return curr-t+1;
	}
	int mid = (l+r)/2;
	push(curr);
	int f = fnd2(a,b,2*curr,l,mid);
	if(f != -1){
		return f;
	}
	return fnd2(a,b,2*curr+1,mid+1,r);
}

int fnd(){
	int pos = fnd2(1,n,1,1,t);
	if(pos > 1){
		if(pos >= k){
			int f = fnd2(pos-k+1,pos-1,1,1,t);
			if(f != -1){
				return f;
			}
		}else{
			int num = k-pos;
			int f = fnd2(n-num,n,1,1,t);
			if(f != -1){
				return f;
			}
			f = fnd2(1,pos-1,1,1,t);
			if(f != -1){
				return f;
			}
		}
	}else{
		int f = fnd2(n-k+2,n,1,1,t);
		if(f != -1){
			return f;
		}
	}
	return pos;
}

void init(int K , vector<int> r){
	n = r.size() , cnt = 0 , k = K;
	t = pow(2,ceil(log2(n)));
	segment.resize(2*t,{0,0});
	for(int i = 0 ; i < (int)r.size() ; i += 1){
		upd(i+1,i+1,r[i],1,1,t);
	}
	for(int i = 0 ; i < n ; i += 1){
		int f = fnd();
		u(f);
	}
}

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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