oj.uz

Submission #400307

# Submission time Handle Problem Language Result Execution time Memory
400307 2021-05-07T20:30:16 Z faresbasbs Comparing Plants (IOI20_plants) C++14
27 / 100
 617 ms 12904 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-1;
			rupd(1,pos-1,1,1,t),rupd(n-num,n,1,1,t);
		}
	}else{
		rupd(n-k+2,n,1,1,t);
	}
}

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-1;
			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
14.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 Correct 1 ms 204 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 72 ms 5124 KB Output is correct
8 Correct 3 ms 320 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 76 ms 5232 KB Output is correct
11 Correct 71 ms 5060 KB Output is correct
12 Correct 69 ms 5224 KB Output is correct
13 Correct 71 ms 5236 KB Output is correct

Subtask #3
13.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 Correct 1 ms 204 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 72 ms 5124 KB Output is correct
8 Correct 3 ms 320 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 76 ms 5232 KB Output is correct
11 Correct 71 ms 5060 KB Output is correct
12 Correct 69 ms 5224 KB Output is correct
13 Correct 71 ms 5236 KB Output is correct
14 Correct 106 ms 6044 KB Output is correct
15 Correct 617 ms 12904 KB Output is correct
16 Correct 102 ms 6052 KB Output is correct
17 Correct 580 ms 12832 KB Output is correct
18 Correct 493 ms 12480 KB Output is correct
19 Correct 493 ms 12872 KB Output is correct
20 Correct 601 ms 12888 KB Output is correct

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 63 ms 3188 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 204 KB Output is correct
3 Incorrect 1 ms 204 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 204 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 -