Submission #899414

#	Time	Username	Problem	Language	Result	Execution time	Memory
899414		ByeWorld	Wall (IOI14_wall)	C++14	100 / 100	724 ms	161180 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
const int MAXN = 2e6+10;
const int INF = 2e9+10;

int n, k;
int ans[MAXN];

struct node {
	int sum;
	int mx, mx2, mxc;
	int mn, mn2, mnc;
} st[4*MAXN];

struct seg {
	void merge(int id){
		st[id].sum = st[lf].sum + st[rg].sum;

		// mx
		if(st[lf].mx == st[rg].mx){
			st[id].mx = st[lf].mx;
			st[id].mxc = st[lf].mxc + st[rg].mxc;

			st[id].mx2 = max(st[lf].mx2, st[rg].mx2);

		} else if(st[lf].mx > st[rg].mx){
			st[id].mx = st[lf].mx;
			st[id].mxc = st[lf].mxc;

			st[id].mx2 = max(st[lf].mx2, st[rg].mx);
		} else {
			// st[lf].mx < st[rg].mx
			st[id].mx = st[rg].mx;
			st[id].mxc = st[rg].mxc;

			st[id].mx2 = max(st[lf].mx, st[rg].mx2);
		}

		// mn 
		if(st[lf].mn == st[rg].mn){
			st[id].mn = st[lf].mn;
			st[id].mnc = st[lf].mnc + st[rg].mnc;

			st[id].mn2 = min(st[lf].mn2, st[rg].mn2);

		} else if(st[lf].mn < st[rg].mn){
			st[id].mn = st[lf].mn;
			st[id].mnc = st[lf].mnc;

			st[id].mn2 = min(st[lf].mn2, st[rg].mn);
		} else {
			// st[lf].mn > st[rg].mn
			st[id].mn = st[rg].mn;
			st[id].mnc = st[rg].mnc;

			st[id].mn2 = min(st[lf].mn, st[rg].mn2);
		}
	}


	void bd(int id, int l, int r){
		if(l==r){ 
			st[id].sum = st[id].mx = st[id].mn = 0; 
			st[id].mx2 = -INF; st[id].mn2 = INF;
			st[id].mxc = st[id].mnc = 1;
			return; 
		}
		bd(lf, l, md); bd(rg, md+1, r);
		merge(id);
		//cout << l << ' ' << r << ' ' << st[id].mx << ' ' << st[id].mx2 << " lrx\n";
	}

	void push_mx(int id, int p, bool len){
		if(p <= st[id].mn) return;
 		st[id].sum += (p-st[id].mn) * st[id].mnc; // jadi makin gede
		st[id].mn = p;

		// mx nya gmn?
		if(len){ // l == r
			st[id].mx = p;
		} else {
			if(p >= st[id].mx) st[id].mx = p;
			else if(p > st[id].mx2) st[id].mx2 = p;
		}
	}
	void push_mn(int id, int p, bool len){
		if(p >= st[id].mx) return;
 		st[id].sum += (p-st[id].mx) * st[id].mxc; // jadi makin kecil, minus
		st[id].mx = p;

		// mn nya gmn?
		if(len){
			st[id].mn = p;
		} else {
			if(p <= st[id].mn) st[id].mn = p;
			else if(p < st[id].mn2) st[id].mn2 = p;
		}
	}

	void bnc(int id, int l, int r){
		if(l == r) return;
		push_mn(lf, st[id].mx, l == md); // new value yg ke prop
		push_mn(rg, st[id].mx, md+1 == r);

		//cout << "here\n";
		push_mx(lf, st[id].mn, l == md); 
		push_mx(rg, st[id].mn, md+1 == r);
	}

	void CHMX(int id, int l, int r, int x, int y, int p){ //a[i] = max(a[i], x);
		if(r<x || y<l || p <= st[id].mn) return; // update gk ganti apa2
		//cout << l << ' ' << r << ' ' << st[id].mn << ' ' << st[id].mn2 << " lr\n";

		if(x<=l && r<=y && p < st[id].mn2){
			push_mx(id, p, l==r);
			return;
		}
		bnc(id, l, r);

		CHMX(lf, l, md, x, y, p); CHMX(rg, md+1, r, x, y, p);
		merge(id);
	}
	void CHMN(int id, int l, int r, int x, int y, int p){ //a[i] = min(a[i], x)
		if(r<x || y<l || p >= st[id].mx) return; // update gk ganti apa2
		//cout << l << ' ' << r << ' ' << st[id].mx << ' ' << st[id].mx2 << " lr\n";
		if(x<=l && r<=y && p > st[id].mx2){ // mx masih ttp mx, tp ganti jadi x -> mx = x
			push_mn(id, p, l==r);
			return;
		}
		bnc(id, l, r);

		CHMN(lf, l, md, x, y, p); CHMN(rg, md+1, r, x, y, p);

		merge(id);
	}	

	void que(int id, int l, int r){
		if(l==r){ 
			ans[l] = st[id].sum; 
			//cout << l << ' ' << ans[l] << " p\n"; 
			return; 
		}
		bnc(id, l, r);
		que(lf, l, md); que(rg, md+1, r);
	}
} A;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	
	A.bd(1, 1, n);
	for(int i=0; i<k; i++){
		if(op[i] == 1){ // add -> a[i] = max(a[i], x);
			A.CHMX(1, 1, n, left[i]+1, right[i]+1, height[i]);
		} else { // remove -> a[i] = min(a[i], x)
			A.CHMN(1, 1, n, left[i]+1, right[i]+1, height[i]);
		}
	}

	A.que(1, 1, n);
	for(int i=1; i<=n; i++) finalHeight[i-1] = ans[i];
	return;
}

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