oj.uz

Submission #793075

# Submission time Handle Problem Language Result Execution time Memory
793075 2023-07-25T13:33:42 Z I_Love_EliskaM_ Wall (IOI14_wall) C++14
100 / 100
 798 ms 149588 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 (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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 6 ms 1492 KB Output is correct
5 Correct 6 ms 1620 KB Output is correct
6 Correct 5 ms 1492 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 107 ms 9340 KB Output is correct
3 Correct 57 ms 6860 KB Output is correct
4 Correct 138 ms 17916 KB Output is correct
5 Correct 141 ms 17984 KB Output is correct
6 Correct 156 ms 17972 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 1492 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 5 ms 1492 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 108 ms 10412 KB Output is correct
9 Correct 61 ms 8064 KB Output is correct
10 Correct 134 ms 19016 KB Output is correct
11 Correct 141 ms 18976 KB Output is correct
12 Correct 157 ms 19132 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 113 ms 10400 KB Output is correct
15 Correct 28 ms 3412 KB Output is correct
16 Correct 476 ms 19016 KB Output is correct
17 Correct 276 ms 18940 KB Output is correct
18 Correct 238 ms 19044 KB Output is correct

Subtask #4
39.0 / 39.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 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1488 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 5 ms 1460 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 117 ms 10368 KB Output is correct
9 Correct 57 ms 7884 KB Output is correct
10 Correct 134 ms 19040 KB Output is correct
11 Correct 139 ms 18996 KB Output is correct
12 Correct 159 ms 19044 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 113 ms 10388 KB Output is correct
15 Correct 28 ms 3432 KB Output is correct
16 Correct 490 ms 19048 KB Output is correct
17 Correct 240 ms 19020 KB Output is correct
18 Correct 242 ms 19164 KB Output is correct
19 Correct 714 ms 149588 KB Output is correct
20 Correct 736 ms 149588 KB Output is correct
21 Correct 781 ms 149464 KB Output is correct
22 Correct 710 ms 149340 KB Output is correct
23 Correct 703 ms 149336 KB Output is correct
24 Correct 715 ms 149328 KB Output is correct
25 Correct 714 ms 149204 KB Output is correct
26 Correct 703 ms 149076 KB Output is correct
27 Correct 798 ms 148636 KB Output is correct
28 Correct 719 ms 148440 KB Output is correct
29 Correct 708 ms 147928 KB Output is correct
30 Correct 757 ms 147416 KB Output is correct