Submission #793075

#	Time	Username	Problem	Language	Result	Execution time	Memory
793075		I_Love_EliskaM_	Wall (IOI14_wall)	C++14	100 / 100	798 ms	149588 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

struct sgt {
	vector<int> mx,mn; int sz=1;
	vector<int> lazy;
	vector<int> type;
	void upd(int v, int t, int x) {
		if (v>=2*sz-1) return;
		if (t==3) {
			type[v]=3;
			lazy[v]=x;
			return;
		}
		if (type[v]==0) {
			type[v]=t;
			lazy[v]=x;
			return;
		}
		if (type[v]==1) {
			if (t==1) {
				lazy[v]=max(lazy[v],x);
				return;
			}
			if (x <= lazy[v]) {
				type[v]=3;
				lazy[v]=x;
			} else {
				mn[v]=max(mn[v],lazy[v]);
				mx[v]=max(mx[v],lazy[v]);
				upd(2*v+1,type[v],lazy[v]);
				upd(2*v+2,type[v],lazy[v]);
				type[v]=2;
				lazy[v]=x;
			}
			return;
		}
		if (type[v]==2) {
			if (t==2) {
				lazy[v]=min(lazy[v],x);
				return;
			}
			if (x >= lazy[v]) {
				type[v]=3;
				lazy[v]=x;
			} else {
				mx[v]=min(mx[v],lazy[v]);
				mn[v]=min(mn[v],lazy[v]);
				upd(2*v+1,type[v],lazy[v]);
				upd(2*v+2,type[v],lazy[v]);
				type[v]=1;
				lazy[v]=x;
			}
			return;
		}
		if (type[v]==3) {
			if (t==1) {
				lazy[v]=max(lazy[v],x);
			} else {
				lazy[v]=min(lazy[v],x);
			}
		}
	}
	void push(int v) {
		upd(2*v+1,type[v],lazy[v]);
		upd(2*v+2,type[v],lazy[v]);
		if (type[v]==1) {
			mn[v]=max(mn[v],lazy[v]);
			mx[v]=max(mx[v],lazy[v]);
		} else if (type[v]==2) {
			mx[v]=min(mx[v],lazy[v]);
			mn[v]=min(mn[v],lazy[v]);
		} else {
			mn[v]=mx[v]=lazy[v];
		}
		type[v]=0;
		lazy[v]=0;
	}
	sgt(int n) {
		while (sz<n) sz<<=1;
		mx.assign(4*sz,0);
		mn=lazy=type=mx;
	}

	void setmax(int v, int l, int r, int lx, int rx, int x) {
		if (type[v]) push(v);
		if (mn[v]>=x) return;
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			upd(v,1,x);
			push(v);
			return;
		}
		int m=(l+r)>>1;
		setmax(2*v+1,l,m,lx,rx,x);
		setmax(2*v+2,m,r,lx,rx,x);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
	}
	void setmax(int l, int r, int x) {
		setmax(0,0,sz,l,r,x);
	}

	void setmin(int v, int l, int r, int lx, int rx, int x) {
		if (type[v]) push(v);
		if (mx[v]<=x) return;
		if (rx<=l || r<=lx) return;
		if (lx<=l && r<=rx) {
			upd(v,2,x);
			push(v);
			return;
		}
		int m=(l+r)>>1;
		setmin(2*v+1,l,m,lx,rx,x);
		setmin(2*v+2,m,r,lx,rx,x);
		mx[v]=max(mx[2*v+1],mx[2*v+2]);
		mn[v]=min(mn[2*v+1],mn[2*v+2]);
	}
	void setmin(int l, int r, int x) {
		setmin(0,0,sz,l,r,x);
	}

	void dfs(int v, int l, int r) {
		if (type[v]) push(v);
		if (r-l==1) return;
		int m=(l+r)>>1;
		dfs(2*v+1,l,m);
		dfs(2*v+2,m,r);
	}
	void dfs() {
		dfs(0,0,sz);
	}

};

void buildWall(int n, int k, int t[], int l[], int r[], int a[], int ans[]) {

	sgt st(n);
	forn(i,k) {
		if (t[i]==1) {
			st.setmax(l[i],r[i]+1,a[i]);
		} else {
			st.setmin(l[i],r[i]+1,a[i]);
		}
	}
	st.dfs();
	forn(i,n) ans[i]=st.mn[st.sz-1+i];

}

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