oj.uz

Submission #428938

# Submission time Handle Problem Language Result Execution time Memory
428938 2021-06-15T15:36:39 Z alireza_kaviani Comparing Plants (IOI20_plants) C++11
27 / 100
 578 ms 16836 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define X		first
#define Y		second
#define lc		id << 1
#define rc		lc | 1

const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;

int n , k , ans = -1 , A[MAXN] , val[MAXN] , lz[MAXN << 2];
pii seg[MAXN << 2];
set<int> st;

void Insert(int x){
	int y = (*prev(st.lower_bound(x))) , z = MOD;
	if(st.lower_bound(x) != st.end())	z = (*st.lower_bound(x));
	if(ans == z && z - x < k)	ans = -1;
	if(x - y >= k)	ans = x;
	st.insert(x);
}

void build(int id = 1 , int l = 0 , int r = n){
	if(r - l == 1){
		seg[id] = {A[l] , l};
		return;
	}
	int mid = l + r >> 1;
	build(lc , l , mid);
	build(rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

void shift(int id){
	lz[lc] += lz[id]; seg[lc].X += lz[id]; 
	lz[rc] += lz[id]; seg[rc].X += lz[id];
	lz[id] = 0;
}

void add(int ql , int qr , int val , int id = 1 , int l = 0 , int r = n){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr && (seg[id].X + val > 0 || r - l == 1)){
		lz[id] += val;
		seg[id].X += val;
		if(seg[id].X == 0)	Insert(l);
		return;
	}
	shift(id);
	int mid = l + r >> 1;
	add(ql , qr , val , lc , l , mid);
	add(ql , qr , val , rc , mid , r);
	seg[id] = min(seg[lc] , seg[rc]);
}

pii get(int ql , int qr , int id = 1 , int l = 0 , int r = n){
	if(qr <= l || r <= ql)	return {MOD , MOD};
	if(ql <= l && r <= qr)	return seg[id];
	shift(id);
	int mid = l + r >> 1;
	return min(get(ql , qr , lc , l , mid) , get(ql , qr , rc , mid , r));
}

void Add(int l , int r , int val){
	if(l < r){
		add(l , r , val);
		return;
	}
	add(0 , r , val); add(l , n , val);
	return;
}

pii Get(int l , int r){
	if(l < r)	return get(l , r);
	pii A = get(0 , r) , B = get(l , n);
	if(A.X < B.X)	return A;
	return B;
}

void init(int K, vector<int> r) {
	k = K; n = r.size();
	for(int i = 0 ; i < n ; i++)	A[i] = r[i];
	build(); st.insert(-1);
	for(int i = 0 ; i < n ; i++){
		if(A[i] == 0){
			Insert(i);
		}
	}
	for(int i = 0 ; i < n ; i++){
		int pos = ans;
		if(pos == -1)	pos = (*st.lower_bound(0));
		//cout << pos << endl;
		st.erase(pos);
		if(st.lower_bound(pos) != st.end()){
			ans = (*st.lower_bound(pos));
			if(ans < k - 1)	ans = -1;
		}
		else	ans = -1;
		Add((pos + n - k + 1) % n , pos , -1);
		Add(pos , pos + 1 , MOD);
		val[pos] = n - i;
	}
	return;
}

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

Compilation message

plants.cpp: In function 'void build(int, int, int)':
plants.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid = l + r >> 1;
      |            ~~^~~
plants.cpp: In function 'void add(int, int, int, int, int, int)':
plants.cpp:53:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid = l + r >> 1;
      |            ~~^~~
plants.cpp: In function 'pii get(int, int, int, int, int)':
plants.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |  int mid = l + r >> 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 332 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 4 ms 332 KB Output is correct
7 Correct 68 ms 3436 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 72 ms 3320 KB Output is correct
11 Correct 75 ms 3376 KB Output is correct
12 Correct 65 ms 3524 KB Output is correct
13 Correct 68 ms 3324 KB Output is correct

Subtask #3
13.0 / 13.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 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 4 ms 332 KB Output is correct
7 Correct 68 ms 3436 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 72 ms 3320 KB Output is correct
11 Correct 75 ms 3376 KB Output is correct
12 Correct 65 ms 3524 KB Output is correct
13 Correct 68 ms 3324 KB Output is correct
14 Correct 98 ms 4136 KB Output is correct
15 Correct 578 ms 12136 KB Output is correct
16 Correct 93 ms 4288 KB Output is correct
17 Correct 511 ms 12180 KB Output is correct
18 Correct 421 ms 16836 KB Output is correct
19 Correct 313 ms 12112 KB Output is correct
20 Correct 511 ms 12260 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 332 KB Output is correct
3 Correct 67 ms 3168 KB Output is correct
4 Correct 307 ms 15272 KB Output is correct
5 Incorrect 357 ms 12732 KB Output isn't correct
6 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 -