제출 #113974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113974		E869120	벽 (IOI14_wall)	C++14	61 / 100	3036 ms	164088 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39