oj.uz

답안 #339738

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339738 2020-12-26T05:44:43 Z oolimry 식물 비교 (IOI20_plants) C++14
11 / 100
 4000 ms 17260 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--;
}

int L[200005];
int R[200005];
int mat[305][305];

ii get(int i){
	if(i < 0) i += n;
	if(i >= n) i -= n;
	return ii(H[i], i);
}

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);
	}
	
	set<ii> Left, Right;
	
	for(int k = 1;k < K;k++){
		Left.insert(get(-k));
		Right.insert(get(k));
	}
		
	for(int i = 0;i < n;i++){
		auto it = Left.upper_bound(ii(H[i],0));
		if(it != Left.begin()){
			it--;
			L[i] = it->second;
		}
		else L[i] = -1;
		
		it = Right.upper_bound(ii(H[i],0));
		if(it != Right.begin()){
			it--;
			R[i] = it->second;
		}
		else R[i] = -1;
		
		Left.erase(get(i-K+1));
		Left.insert(get(i));
		Right.erase(get(i+1));
		Right.insert(get(i+K));
	}
	
	for(int i = 0;i < n;i++){
		mat[i][L[i]] = 1;
		mat[i][R[i]] = 1;
	}
	
	for(int k = 0;k < n;k++) for(int i = 0;i < n;i++) for(int j = 0;j < n;j++){
		mat[i][j] |= (mat[i][k] & mat[k][j]);
	}
		
	return;
}

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

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:75:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   75 |  if(L < 0) L += n; if(R < 0) R += n;
      |  ^~
plants.cpp:75:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   75 |  if(L < 0) L += n; if(R < 0) R += n;
      |                    ^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 60 ms 4332 KB Output is correct
7 Runtime error 79 ms 17260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Incorrect 877 ms 1856 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Incorrect 877 ms 1856 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Execution timed out 4067 ms 7148 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 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 3 ms 620 KB Output is correct
7 Correct 40 ms 1644 KB Output is correct
8 Correct 40 ms 1772 KB Output is correct
9 Correct 39 ms 1644 KB Output is correct
10 Correct 44 ms 1644 KB Output is correct
11 Correct 41 ms 1644 KB Output is correct
12 Correct 40 ms 1644 KB Output is correct
13 Correct 39 ms 1772 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 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 Incorrect 880 ms 1772 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 60 ms 4332 KB Output is correct
7 Runtime error 79 ms 17260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -