Submission #1101796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101796		pubin06	Wall (IOI14_wall)	C++14	100 / 100	724 ms	69476 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
using namespace std;

const int MXn = 2e6 + 5, oo = 1e5;

int N;
struct type {
	int LL, RR;
} node[(1 << 22) + 5];
void build(int id = 1, int l = 0, int r = N) {
	if (l == r) {
		node[id] = {0, 0};
		return;
	}
	node[id] = {0, oo};
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
}
void modify(int id, int t, int val) {
	// if (val == 3 && id == 24) cerr << t << ' ' << node[id].LL << ' ' << node[id].RR << '\n';
	if (t == 1) {
		// if (node[id].RR < val) node[id].b = true;
		node[id].LL = max(node[id].LL, val);
		node[id].RR = max(node[id].RR, val);
	} else {
		// if (node[id].LL > val) node[id].b = false;
		node[id].LL = min(node[id].LL, val);
		node[id].RR = min(node[id].RR, val);
	}
	// if (val == 3 && id == 24) cerr << t << ' ' << node[id].LL << ' ' << node[id].RR << '\n';
}
void push(int id) {
	// if (node[id].b) {
		modify(id << 1, 1, node[id].LL);
		modify(id << 1, 2, node[id].RR);
		modify(id << 1 | 1, 1, node[id].LL);
		modify(id << 1 | 1, 2, node[id].RR);
	// } else {
		// modify(id << 1, 2, node[id].LL);
		// modify(id << 1, 1, node[id].RR);
		// modify(id << 1 | 1, 2, node[id].LL);
		// modify(id << 1 | 1, 1, node[id].RR);
	// }
	node[id] = {0, oo};
}
void update(int t, int Lf, int Rt, int val, int id = 1, int l = 0, int r = N) {
	if (Lf <= l && r <= Rt) {
		modify(id, t, val);
		return;
	}
	push(id);
	int mid = (l + r) >> 1;
	if (Lf <= mid) update(t, Lf, Rt, val, id << 1, l, mid);
	if (Rt > mid) update(t, Lf, Rt, val, id << 1 | 1, mid + 1, r);
}
int findh(int i) {
	int id = 1, l = 0, r = N;
	while (l < r) {
		push(id);
		int mid = (l + r) >> 1;
		if (i <= mid) {
			id <<= 1;
			r = mid;
		} else {
			id = id << 1 | 1;
			l = mid + 1;
		}
	}
	return node[id].LL;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	N = n - 1;
	build();
	for (int i = 0; i < k; i++) update(op[i], left[i], right[i], height[i]);
	for (int i = 0; i < n; i++) finalHeight[i] = findh(i);
}

// int main()
// {
  // int n;
  // int k;
// 
  // int i, j;  
  // int status = 0;
// 
  // status = scanf("%d%d", &n, &k);
  // assert(status == 2);
// 
  // int* op = (int*)calloc(sizeof(int), k);
  // int* left = (int*)calloc(sizeof(int), k);
  // int* right = (int*)calloc(sizeof(int), k);
  // int* height = (int*)calloc(sizeof(int), k);
  // int* finalHeight = (int*)calloc(sizeof(int), n);
// 
  // for (i = 0; i < k; i++){
    // status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    // assert(status == 4);
  // }
// 
  // buildWall(n, k, op, left, right, height, finalHeight);
// 
  // for (j = 0; j < n; j++)
    // printf("%d\n", finalHeight[j]);
//   
  // return 0;
// }

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39