Submission #678708

#	Time	Username	Problem	Language	Result	Execution time	Memory
678708		penguin133	Wall (IOI14_wall)	C++17	8 / 100	112 ms	8096 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

vector< pii > up, down;

struct node{
	int s, e, m, val, lazy;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	
	void propo(){
		if(lazy){
			val = lazy;
			if(s != e)l->lazy = lazy, r->lazy = lazy;
			lazy = 0;
		}
	}
	
	void upd(int a, int b, int c){
		if(a == s && b == e)lazy = c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->propo(), r->propo();
		}
	}
	int query(int p){
		propo();
		if(s == e)return val;
		else if(p <= m)return l->query(p);
		else return r->query(p);
	}
}*root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<n;i++)finalHeight[i] = 0;
	if(n <= 10000 && k <= 5000){	
		for(int i=0;i<k;i++){
			if(op[i] == 1){
				for(int j=left[i];j<=right[i];j++)finalHeight[j] = max(finalHeight[j], height[i]);
			}
			else{
				for(int j=left[i];j<=right[i];j++)finalHeight[j] = min(finalHeight[j], height[i]);
			}
		}
		return;
	}
	root = new node(0, n-1);
	for(int i=0;i<n;i++){
		if(op[i] == 1)up.push_back({height[i], {left[i], right[i]}});
		else down.push_back({height[i], {left[i], right[i]}});
	}
	sort(up.begin(), up.end());
	for(auto i : up)root->upd(i.se.fi, i.se.se, i.fi);
	for(int i=0;i<n;i++){
		int x = root->query(i);
		down.push_back({x, {i, i}});
	}
	sort(down.begin(), down.end(), greater<>());
	for(auto i : down)root->upd(i.se.fi, i.se.se, i.fi);
	for(int i=0;i<n;i++)finalHeight[i] = root->query(i);
}

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