oj.uz

Submission #793077

# Submission time Handle Problem Language Result Execution time Memory
793077 2023-07-25T13:34:18 Z TimDee Wall (IOI14_wall) C++17
100 / 100
 799 ms 147376 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 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 107 ms 8028 KB Output is correct
3 Correct 68 ms 5572 KB Output is correct
4 Correct 137 ms 16744 KB Output is correct
5 Correct 138 ms 16648 KB Output is correct
6 Correct 152 ms 16728 KB Output is correct

Subtask #3
29.0 / 29.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 1 ms 340 KB Output is correct
4 Correct 6 ms 1440 KB Output is correct
5 Correct 7 ms 1440 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 128 ms 8040 KB Output is correct
9 Correct 69 ms 5636 KB Output is correct
10 Correct 130 ms 16688 KB Output is correct
11 Correct 145 ms 16636 KB Output is correct
12 Correct 153 ms 16716 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 126 ms 8076 KB Output is correct
15 Correct 27 ms 2884 KB Output is correct
16 Correct 478 ms 16740 KB Output is correct
17 Correct 235 ms 16708 KB Output is correct
18 Correct 253 ms 16688 KB Output is correct

Subtask #4
39.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 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 106 ms 8076 KB Output is correct
9 Correct 58 ms 5580 KB Output is correct
10 Correct 130 ms 16692 KB Output is correct
11 Correct 160 ms 16712 KB Output is correct
12 Correct 153 ms 16656 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 112 ms 8080 KB Output is correct
15 Correct 27 ms 2892 KB Output is correct
16 Correct 512 ms 16740 KB Output is correct
17 Correct 247 ms 16736 KB Output is correct
18 Correct 247 ms 16744 KB Output is correct
19 Correct 726 ms 147292 KB Output is correct
20 Correct 752 ms 147292 KB Output is correct
21 Correct 708 ms 147288 KB Output is correct
22 Correct 792 ms 147376 KB Output is correct
23 Correct 741 ms 147288 KB Output is correct
24 Correct 734 ms 147280 KB Output is correct
25 Correct 724 ms 147196 KB Output is correct
26 Correct 772 ms 147284 KB Output is correct
27 Correct 799 ms 147288 KB Output is correct
28 Correct 707 ms 147288 KB Output is correct
29 Correct 776 ms 147360 KB Output is correct
30 Correct 725 ms 147280 KB Output is correct