oj.uz

Submission #793055

# Submission time Handle Problem Language Result Execution time Memory
793055 2023-07-25T13:08:02 Z I_Love_EliskaM_ Wall (IOI14_wall) C++14
24 / 100
 169 ms 27236 KB 
#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 (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]);
				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]);
				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 h[], int ans[]) {

	sgt st(n);
	vector<int> a(n);
	forn(i,k) {
		if (t[i]==1) {
			st.setmax(l[i],r[i]+1,h[i]);
			//for(int j=l[i];j<=r[i];++j) a[i]=max(a[i],h[i]);
		} else {
			st.setmin(l[i],r[i]+1,h[i]);
			//for(int j=l[i];j<=r[i];++j) a[i]=min(a[i],h[i]);
		}

		//st.dfs();
		//forn(j,n) cout<<st.mn[st.sz-1+j]<<' '; cout<<'\n';
		//forn(j,n) cout<<st.mx[st.sz-1+j]<<' '; cout<<'\n';
	}
	st.dfs();
	forn(i,n) ans[i]=st.mn[st.sz-1+i];

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 116 ms 8040 KB Output is correct
3 Correct 68 ms 5640 KB Output is correct
4 Correct 141 ms 17108 KB Output is correct
5 Correct 145 ms 27236 KB Output is correct
6 Correct 169 ms 25724 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -