답안 #113976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113976 2019-05-29T12:13:59 Z E869120 벽 (IOI14_wall) C++14
100 / 100
2347 ms 174740 KB
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

class RangeMin {
	public:
	vector<int>dat; int size_ = 1;
	
	void init(int sz, int t) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, t);
	}
	void update(int pos, int x) {
		pos += size_;
		dat[pos] = x;
		while (pos >= 2) {
			pos >>= 1;
			dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
		}
	}
	int query_(int l, int r, int a, int b, int u) {
		//cout << l << " " << r << " " << a << " " << b << " " << u << " " << dat.size() << endl;
		if (l <= a) return dat[u];
		if (b <= l) return (1 << 30);
		
		int v1 = query_(l, r, a, (a + b) >> 1, u * 2);
		int v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return min(v1, v2);
	}
	int query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

int N, Q, ty[1 << 21], L[1 << 21], R[1 << 21], H[1 << 21];
RangeMin AL, AR;
vector<int> E[1 << 21][2];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	N = n; Q = k;
	for (int i = 1; i <= Q; i++) { ty[i] = op[i - 1]; L[i] = left[i - 1]; R[i] = right[i - 1]; H[i] = height[i - 1]; }
	
	AL.init(Q + 2, 0);
	AR.init(Q + 2, 1000000);
	for (int i = 1; i <= Q; i++) { E[L[i]][0].push_back(i); E[R[i]][1].push_back(i); }
	
	for (int i = 0; i < N; i++) {
		for (int pos : E[i][0]) { if (ty[pos] == 1) AL.update(pos, -H[pos]); if (ty[pos] == 2) AR.update(pos, H[pos]); }
		
		int G = AL.size_, S = 0;
		for (int i = (G >> 1); i >= 1; i >>= 1) {
			int SS = S + i;
			int P1 = -AL.query(SS, G);
			int P2 = AR.query(SS, G);
			if (P1 > P2) { S += i; }
		}
		
		if (S == 0) {
			finalHeight[i] = -AL.query(0, G);
		}
		else {
			int V1 = -AL.query(S, G);
			int V2 = AR.query(S, G);
			if (V1 == H[S]) finalHeight[i] = V2;
			else finalHeight[i] = V1;
		}
		
		for (int pos : E[i][1]) { if (ty[pos] == 1) AL.update(pos, 0); if (ty[pos] == 2) AR.update(pos, 1000000); }
	}
}

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 98808 KB Output is correct
2 Correct 89 ms 99292 KB Output is correct
3 Correct 96 ms 98936 KB Output is correct
4 Correct 105 ms 99448 KB Output is correct
5 Correct 95 ms 99492 KB Output is correct
6 Correct 94 ms 99516 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 98780 KB Output is correct
2 Correct 285 ms 126960 KB Output is correct
3 Correct 250 ms 113016 KB Output is correct
4 Correct 788 ms 132856 KB Output is correct
5 Correct 396 ms 131176 KB Output is correct
6 Correct 387 ms 131032 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 98868 KB Output is correct
2 Correct 96 ms 99288 KB Output is correct
3 Correct 90 ms 98936 KB Output is correct
4 Correct 96 ms 99492 KB Output is correct
5 Correct 98 ms 99364 KB Output is correct
6 Correct 95 ms 99400 KB Output is correct
7 Correct 84 ms 98808 KB Output is correct
8 Correct 284 ms 126888 KB Output is correct
9 Correct 251 ms 112888 KB Output is correct
10 Correct 771 ms 132920 KB Output is correct
11 Correct 410 ms 131192 KB Output is correct
12 Correct 390 ms 130944 KB Output is correct
13 Correct 84 ms 98808 KB Output is correct
14 Correct 284 ms 126940 KB Output is correct
15 Correct 116 ms 101368 KB Output is correct
16 Correct 836 ms 132956 KB Output is correct
17 Correct 401 ms 130552 KB Output is correct
18 Correct 398 ms 130260 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 98796 KB Output is correct
2 Correct 93 ms 99192 KB Output is correct
3 Correct 88 ms 99036 KB Output is correct
4 Correct 97 ms 99448 KB Output is correct
5 Correct 98 ms 99444 KB Output is correct
6 Correct 95 ms 99448 KB Output is correct
7 Correct 85 ms 98808 KB Output is correct
8 Correct 427 ms 126940 KB Output is correct
9 Correct 275 ms 112928 KB Output is correct
10 Correct 794 ms 132904 KB Output is correct
11 Correct 422 ms 131192 KB Output is correct
12 Correct 398 ms 130812 KB Output is correct
13 Correct 88 ms 98876 KB Output is correct
14 Correct 295 ms 126952 KB Output is correct
15 Correct 127 ms 101340 KB Output is correct
16 Correct 906 ms 133164 KB Output is correct
17 Correct 415 ms 130692 KB Output is correct
18 Correct 412 ms 130248 KB Output is correct
19 Correct 2302 ms 164316 KB Output is correct
20 Correct 2266 ms 172244 KB Output is correct
21 Correct 2306 ms 174688 KB Output is correct
22 Correct 2247 ms 172236 KB Output is correct
23 Correct 2246 ms 172172 KB Output is correct
24 Correct 2309 ms 172304 KB Output is correct
25 Correct 2329 ms 172408 KB Output is correct
26 Correct 2337 ms 174624 KB Output is correct
27 Correct 2347 ms 174740 KB Output is correct
28 Correct 2251 ms 172220 KB Output is correct
29 Correct 2231 ms 172288 KB Output is correct
30 Correct 2285 ms 172352 KB Output is correct