제출 #123409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123409		ekrem	벽 (IOI14_wall)	C++98	100 / 100	947 ms	69652 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas + son)/2)
#define sol (k+k)
#define sag (k+k+1)
#define inf 1000000007
#define N 2000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n;
ii seg[4*N];


void put(int k, int bas, int son, int op, int z){
	// cout << op << endl;
	// cout << "BAK" << bas << " " << son << " " << seg[k].st << " " << seg[k].nd << endl;
	if(op == 1){
		if(z >= seg[k].nd)
			seg[k] = mp(z, z);
		if(z >= seg[k].st)
			seg[k].st = z;
	}
	if(op == 0){
		if(z <= seg[k].st)
			seg[k] = mp(z, z);
		if(z <= seg[k].nd){
			seg[k].nd = z;
			// cout << z << " yaptim amk" << endl;
		}
	}
	// cout << "AMK" << bas << " " << son << " " << seg[k].st << " " << seg[k].nd << endl;
}

void push(int k, int bas, int son){
	if(seg[k].st != 0){
		put(sol, bas, orta, 1, seg[k].st);
		put(sag, orta + 1, son, 1, seg[k].st);
	}
	if(seg[k].nd != inf){
		put(sol, bas, orta, 0, seg[k].nd);
		put(sag, orta + 1, son, 0, seg[k].nd);
	}
	seg[k] = mp(0, inf);
}

void up(int k, int bas, int son, int x, int y, int op, int z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		put(k, bas, son, op, z);
		return;
	}
	push(k, bas, son);
	up(sol, bas, orta, x, y, op, z);
	up(sag, orta + 1, son, x, y, op, z);
	// seg[k].st = min(seg[sol].st, seg[sag].st);
	// seg[k].nd = max(seg[sol].nd, seg[sag].nd);
}

int qu(int k, int bas, int son, int x){
	if(bas == son){
		// if(seg[k].st != seg[k].nd){
		// 	cout << "OF MAK " << seg[k].st << " " << seg[k].nd << endl;
		// }
		return seg[k].st;
	}
	push(k, bas, son);
	if(x <= orta)
		return qu(sol, bas, orta, x);
	else
		return qu(sag, orta + 1, son, x);
}

void bu(int k, int bas, int son){
	if(bas == son){
		seg[k] = mp(0, inf);
		return;
	}
	bu(sol, bas, orta);
	bu(sag, orta + 1, son);
	seg[k] = mp(0, inf);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	bu(1, 1, n);
	for(int i = 0; i < k; i++){
		// printf("%d %d %d %d\n", left[i] + 1, right[i] + 1, op[i], height[i] );
		up(1, 1, n, left[i] + 1, right[i] + 1, 2 - op[i], height[i]);
	}
	for(int i = 1; i <= n; i++)
		finalHeight[i - 1] = qu(1, 1, n, i);
	return;
}

// int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// 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