oj.uz

Submission #339409

# Submission time Handle Problem Language Result Execution time Memory
339409 2020-12-25T07:45:38 Z oolimry Comparing Plants (IOI20_plants) C++14
44 / 100
 768 ms 29932 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) x.size();
using namespace std;
typedef pair<int,int> ii;

struct node{
	int s, e, m;
	ii val = ii(0,0); int lazy = 0;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		if(s == e) val = ii(0, S);
		else{
			l = new node(s, m);
			r = new node(m+1, e);
			val = min(l->val, r->val);
		}
	}
	
	void apply(int L){
		val.first += L;
		lazy += L;
	}
	void push(){
		if(s == e) return;
		l->apply(lazy);
		r->apply(lazy);
		lazy = 0;
	}
	
	void update(int S, int E, int L){
		push();
		if(s == S && E == e){
			apply(L);
			return;
		}
		else if(E <= m) l->update(S, E, L);
		else if(S >= m+1) r->update(S, E, L);
		else l->update(S, m, L), r->update(m+1, E, L);
		val = min(l->val, r->val);
	}
	
	ii query(int S, int E){
		push();
		if(s == S && E == e) return val;
		else if(E <= m) return l->query(S, E);
		else if(S >= m+1) return r->query(S, E);
		else return min(l->query(S, m), r->query(m+1, E));
	}
} *root;


int n, K;
int H[200005];
int height;

void assign(int u){
	while(true){
		int R = u-1, L = u-K+1;
		if(L < 0) L += n; if(R < 0) R += n;
		
		ii res;
		if(L <= R){
			res = root->query(L,R);
		}
		else{
			res = min(root->query(L, n-1), root->query(0,R));
		}
		if(res.first == 0) assign(res.second);
		else break;
	}
	
	H[u] = height;
	int R = u-1, L = u-K+1;
	if(L < 0) L += n; if(R < 0) R += n;
	
	if(L <= R){
		root->update(L, R, -1);
	}
	else{
		root->update(L, n-1, -1); root->update(0, R, -1);
	}
	root->update(u, u, 1e9);
	height--;
}

void init(int _K, vector<int> R) {
	n = sz(R); K = _K;
	
	root = new node(0, n-1);
	for(int i = 0;i < n;i++) root->update(i,i,R[i]);
	
	fill(H,H+n,-1);
	height = n-1;
	while(height >= 0){
		ii res = root->query(0, n-1);
		assign(res.second);
	}
	//for(int i = 0;i < n;i++) cout << H[i] << " ";
		
	return;
}

int compare_plants(int x, int y) {
	if(H[x] > H[y]) return 1;
	else return -1;
}

Compilation message

plants.cpp: In function 'void assign(int)':
plants.cpp:63:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   63 |   if(L < 0) L += n; if(R < 0) R += n;
      |   ^~
plants.cpp:63:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |   if(L < 0) L += n; if(R < 0) R += n;
      |                     ^~
plants.cpp:78:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   78 |  if(L < 0) L += n; if(R < 0) R += n;
      |  ^~
plants.cpp:78:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   78 |  if(L < 0) L += n; if(R < 0) R += n;
      |                    ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 72 ms 5612 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 71 ms 5584 KB Output is correct
11 Correct 67 ms 5484 KB Output is correct
12 Correct 68 ms 5740 KB Output is correct
13 Correct 70 ms 5612 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 72 ms 5612 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 71 ms 5584 KB Output is correct
11 Correct 67 ms 5484 KB Output is correct
12 Correct 68 ms 5740 KB Output is correct
13 Correct 70 ms 5612 KB Output is correct
14 Correct 108 ms 7532 KB Output is correct
15 Correct 760 ms 27744 KB Output is correct
16 Correct 107 ms 7532 KB Output is correct
17 Correct 768 ms 27712 KB Output is correct
18 Correct 429 ms 27116 KB Output is correct
19 Correct 434 ms 27688 KB Output is correct
20 Correct 665 ms 27664 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 68 ms 5100 KB Output is correct
4 Correct 352 ms 29932 KB Output is correct
5 Correct 419 ms 27372 KB Output is correct
6 Correct 640 ms 27244 KB Output is correct
7 Correct 744 ms 27372 KB Output is correct
8 Correct 765 ms 27500 KB Output is correct
9 Correct 371 ms 27116 KB Output is correct
10 Correct 366 ms 26860 KB Output is correct
11 Correct 297 ms 26860 KB Output is correct
12 Correct 349 ms 26988 KB Output is correct
13 Correct 419 ms 26988 KB Output is correct

Subtask #5
0 / 11.0

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