Submission #722621

#	Time	Username	Problem	Language	Result	Execution time	Memory
722621		penguin133	Wall (IOI14_wall)	C++17	24 / 100	737 ms	18544 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
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node{
	int s, e, m, val, mx, mn;
	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);
		val = mx = 0 ;
		mn = 2e9;
	}
	
	void prop(){
		if(mx)val = max(val, mx);
		if(mn != 2e9)val = min(val, mn);
		if(s != e){
			if(mx)l->mx = max(mx, l->mx), r->mx = max(mx, r->mx);
			if(mn != 2e9)l->mn = min(l->mn, mn), r->mn = min(r->mn, mn);
		}
		mx = 0; mn = 2e9;
	}
	
	void upd(int a, int b, int c, bool d){
		//cerr << "UPD " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
		prop();
		if(a == s && b == e){
			if(!d)mx = max(mx, c);
			else mn = min(mn, c);
			return;
		}
		if(b <= m)l->upd(a, b, c, d);
		else if(a > m)r->upd(a, b, c, d);
		else l->upd(a, m, c, d), r->upd(m+1, b, c, d);
		l->prop(), r->prop();
		
	}
	
	int qry(int x){
		prop();
		if(s == e)return val;
		if(x <= m)return l->qry(x);
		else return r->qry(x);
	}
}*root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	root = new node(0, n - 1);
	//cerr << "ok\n";
	for(int i=0;i<k;i++){
		if(op[i] == 1)root->upd(left[i], right[i], height[i], 0);
		else root->upd(left[i], right[i], height[i], 1);
		//cerr << "what\n";
	}
	//cerr << "ok\n";
	for(int i=0;i<n;i++)finalHeight[i] = root->qry(i);
}

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