oj.uz

답안 #113974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113974 2019-05-29T12:12:49 Z E869120 벽 (IOI14_wall) C++14
61 / 100
 3000 ms 164088 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 && b <= r) return dat[u];
		if (r <= a || 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); }
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 98808 KB Output is correct
2 Correct 85 ms 99204 KB Output is correct
3 Correct 83 ms 98936 KB Output is correct
4 Correct 100 ms 99448 KB Output is correct
5 Correct 95 ms 99448 KB Output is correct
6 Correct 97 ms 99460 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 98836 KB Output is correct
2 Correct 282 ms 127032 KB Output is correct
3 Correct 247 ms 112948 KB Output is correct
4 Correct 830 ms 132960 KB Output is correct
5 Correct 445 ms 141336 KB Output is correct
6 Correct 434 ms 139384 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 98808 KB Output is correct
2 Correct 84 ms 99136 KB Output is correct
3 Correct 83 ms 99052 KB Output is correct
4 Correct 94 ms 99548 KB Output is correct
5 Correct 94 ms 99456 KB Output is correct
6 Correct 97 ms 99320 KB Output is correct
7 Correct 87 ms 98808 KB Output is correct
8 Correct 290 ms 126912 KB Output is correct
9 Correct 264 ms 113016 KB Output is correct
10 Correct 847 ms 132764 KB Output is correct
11 Correct 466 ms 141348 KB Output is correct
12 Correct 455 ms 139464 KB Output is correct
13 Correct 135 ms 98808 KB Output is correct
14 Correct 311 ms 132668 KB Output is correct
15 Correct 128 ms 102008 KB Output is correct
16 Correct 1235 ms 142712 KB Output is correct
17 Correct 457 ms 139688 KB Output is correct
18 Correct 468 ms 139440 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 98808 KB Output is correct
2 Correct 91 ms 99192 KB Output is correct
3 Correct 87 ms 98936 KB Output is correct
4 Correct 101 ms 99400 KB Output is correct
5 Correct 95 ms 99424 KB Output is correct
6 Correct 94 ms 99420 KB Output is correct
7 Correct 83 ms 98812 KB Output is correct
8 Correct 283 ms 126940 KB Output is correct
9 Correct 257 ms 112892 KB Output is correct
10 Correct 847 ms 132808 KB Output is correct
11 Correct 443 ms 141304 KB Output is correct
12 Correct 440 ms 139364 KB Output is correct
13 Correct 84 ms 98808 KB Output is correct
14 Correct 298 ms 132760 KB Output is correct
15 Correct 137 ms 101976 KB Output is correct
16 Correct 943 ms 142792 KB Output is correct
17 Correct 470 ms 139640 KB Output is correct
18 Correct 482 ms 139308 KB Output is correct
19 Execution timed out 3036 ms 164088 KB Time limit exceeded
20 Halted 0 ms 0 KB -