Submission #553634

#	Time	Username	Problem	Language	Result	Execution time	Memory
553634		keta_tsimakuridze	Wall (IOI14_wall)	C++14	100 / 100	993 ms	99392 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2e6 + 5, inf = 1e9;
struct node{
	int l, r;
} lazy[4 * N];
void down(node &a, node b) {
	if(a.l >= b.r) {
		a = {b.r, b.r};
		return;
	}
	if(a.r <= b.l) {
		a = {b.l, b.l};
		return;
	}
	a.l = max(a.l, b.l); a.r = min(a.r, b.r);
	assert(a.l <= a.r);
}
void push(int u, int l,int r) {
	if(lazy[u].l == 0 && lazy[u].r == inf) return;
	if(l == r) return; 
	down(lazy[2 * u], lazy[u]);
	down(lazy[2 * u + 1], lazy[u]);
	lazy[u] = {0, inf};
}
void upd(int u, int st, int en, int l,int r, int v, int t) {
	push(u, l, r);
	if(l > en || r < st) return;
	if(st <= l && r <= en) { 
		if(l == r) {
			if(!t) {
				lazy[u].l = max(lazy[u].l, v);
				lazy[u].r = max(lazy[u].r, v);
			}
			else {
				lazy[u].l = min(lazy[u].l, v);
				lazy[u].r = min(lazy[u].r, v);				
			} 
			return;
		}
		if(!t) lazy[u].l = v;
		else lazy[u].r = v;
		push(u, l, r);
		return;
	}
	int mid = (l + r) >> 1;
	upd(2 * u, st, en, l, mid, v, t); 
	upd(2 * u + 1,st, en, mid + 1, r, v,t);
}
int get(int u,int ind, int l,int r){
	push(u, l, r);
	if(l == r) return lazy[u].l;
	int mid = (l + r) / 2;
	if(ind <= mid) return get(2 * u, ind, l, mid);
	else return get(2 * u + 1, ind, mid + 1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ih[]){
  
  for(int i = 1; i <= 4 * n; i++) lazy[i] = {0, inf};
  --n;
  for(int i = 0; i < k; i++) {
  	upd(1, l[i], r[i], 0, n, h[i], --op[i]);
  }
 
  for(int i = 0; i <= n; i++) {
  	ih[i] = get(1, i, 0, n);
  }
}

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