제출 #881195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881195		BBart888	벽 (IOI14_wall)	C++14	0 / 100	108 ms	8380 KiB

wall

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"



using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;



const int INF = 2147483640;
const int MAXN = 2e6 + 111;
const int MAXS = 1e5 + 111;
const long long P = 31;
using ll = long long;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;



int n;
pair<int, int> lazy[4 * MAXN];
int mi[4 * MAXN];
int mx[MAXN * 4];
int res[MAXN];


void pull_add(int v, int k)
{
	mi[v] = max(mi[v], k);
	mx[v] = max(mx[v], k);
	lazy[v].first = max(lazy[v].first, k);
	lazy[v].second = max(lazy[v].second, k);
}


void pull_dec(int v, int k)
{
	mi[v] = min(mi[v], k);
	mx[v] = min(mx[v], k);
	lazy[v].first = min(lazy[v].first, k);
	lazy[v].second = min(lazy[v].second, k);
}

void shift(int v)
{
	if (lazy[v].first != -1e9)
	{
		pull_add(2 * v, lazy[v].first);
		pull_add(2 * v + 1, lazy[v].first);
	}
	else if (lazy[v].second != -1e9)
	{
		pull_dec(2 * v, lazy[v].second);
		pull_dec(2 * v + 1, lazy[v].second);
	}
	lazy[v] = { -1e9,1e9 };
}


void upd(int v, int tl, int tr, int l, int r, int type, int val)
{
	if (tl == l && tr == r)
	{
		if (type == 1)
		{
			pull_add(v, val);
		}
		else
		{
			pull_dec(v, val);
		}
		return;
	}
	if (l > r)
		return;
	shift(v);
	int tm = (tl + tr) / 2;
	upd(2 * v, tl, tm, l, min(r, tm), type, val);
	upd(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, type, val);
	mi[v] = min(mi[2 * v], mi[2 * v + 1]);
	mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}

int get(int v, int tl, int tr, int pos)
{
	if (tl == tr)
		return mi[v];
	else
	{
		shift(v);
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			return get(2 * v, tl, tm, pos);
		else
			return get(2 * v + 1, tm + 1, tr, pos);
	}
}







void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for (int i = 0; i < n; i++)
	{
		upd(1, 0, MAXN, left[i], right[i] + 1, op[i],height[i]);
	}

	for (int i = 0; i < n; i++)
		finalHeight[i] = get(1, 0, MAXN, i);
}

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