oj.uz

Submission #784595

# Submission time Handle Problem Language Result Execution time Memory
784595 2023-07-16T10:35:31 Z FatihSolak Wall (IOI14_wall) C++17
100 / 100
 784 ms 141192 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
struct SegTree{
	struct node{
		int mini1,mini2;
		int maxi1,maxi2;
		node():mini1(0),mini2(INF),maxi1(0),maxi2(-INF){}
		void setmax(int x){
			if(x <= mini1)
				return;
			mini1 = x;
			if(maxi1 <= x){
				maxi1 = x;
				maxi2 = -INF;
				mini2 = INF;
			}
			else if(maxi2 < x){
				maxi2 = x;
			}
		}
		void setmin(int x){
			if(x >= maxi1)
				return;
			maxi1 = x;
			if(mini1 >= x){
				mini1 = x;
				maxi2 = -INF;
				mini2 = INF;
			}
			else if(mini2 > x){
				mini2 = x;
			}
		}		
	};
	node merge(node a,node b){
		if(a.maxi1 == b.maxi1){
			a.maxi2 = max(a.maxi2,b.maxi2);
		}
		else{
			if(a.maxi1 > b.maxi1){
				a.maxi2 = max(a.maxi2,b.maxi1);
			}
			else{
				a.maxi2 = max(a.maxi1,b.maxi2);
				a.maxi1 = b.maxi1;
			}
		}

		if(a.mini1 == b.mini1){
			a.mini2 = min(a.mini2,b.mini2);
		}
		else{
			if(a.mini1 < b.mini1){
				a.mini2 = min(a.mini2,b.mini1);
			}
			else{
				a.mini2 = min(a.mini1,b.mini2);
				a.mini1 = b.mini1;
			}
		}
		return a;
	}
	vector<node> t;
	int n;
	SegTree(int sz){
		n = sz;
		t.assign(4*n,node());
	}
	void push(int v){
		t[v*2].setmax(t[v].mini1);
		t[v*2].setmin(t[v].maxi1);
		t[v*2 + 1].setmax(t[v].mini1);
		t[v*2 + 1].setmin(t[v].maxi1);
	}
	void upd(int v,int tl,int tr,int l,int r,int val,int op){
		if(tr < l || r < tl || (op == 1 && t[v].mini1 >= val) || (op == 2 && t[v].maxi1 <= val)){
			return;
		}
		if(l <= tl && tr <= r && ((op == 1 && t[v].mini2 > val) || (op == 2 && t[v].maxi2 < val))){
			if(op == 1){
				t[v].setmax(val);
			}
			else t[v].setmin(val);
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val,op);
		upd(v*2 + 1,tm+1,tr,l,r,val,op);
		t[v] = merge(t[v*2],t[v*2+1]);
	}
	int get(int v,int tl,int tr,int pos){
		if(tl == tr){
			return t[v].maxi1;
		}
		push(v);
		int tm = (tl + tr)/2;
		if(pos <= tm){
			return get(v*2,tl,tm,pos);
		}
		return get(v*2+1,tm+1,tr,pos);
	}
	void upd(int l,int r,int val,int op){
		upd(1,0,n-1,l,r,val,op);
	}
	int get(int pos){
		return get(1,0,n-1,pos);
	}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree t(n);
	for(int i = 0;i<k;i++){
		t.upd(left[i],right[i],height[i],op[i]);
	}
	for(int i = 0;i<n;i++){
		finalHeight[i] = t.get(i);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 6 ms 1024 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 980 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 97 ms 8008 KB Output is correct
3 Correct 53 ms 4632 KB Output is correct
4 Correct 145 ms 14688 KB Output is correct
5 Correct 142 ms 14700 KB Output is correct
6 Correct 164 ms 14776 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 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 99 ms 8096 KB Output is correct
9 Correct 52 ms 4648 KB Output is correct
10 Correct 136 ms 14756 KB Output is correct
11 Correct 141 ms 14680 KB Output is correct
12 Correct 162 ms 14720 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 179 ms 8012 KB Output is correct
15 Correct 28 ms 1876 KB Output is correct
16 Correct 455 ms 14740 KB Output is correct
17 Correct 249 ms 14668 KB Output is correct
18 Correct 239 ms 14684 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 380 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 106 ms 8080 KB Output is correct
9 Correct 55 ms 4740 KB Output is correct
10 Correct 137 ms 14728 KB Output is correct
11 Correct 142 ms 14736 KB Output is correct
12 Correct 158 ms 14668 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 103 ms 8008 KB Output is correct
15 Correct 27 ms 1892 KB Output is correct
16 Correct 453 ms 14680 KB Output is correct
17 Correct 257 ms 14780 KB Output is correct
18 Correct 241 ms 14784 KB Output is correct
19 Correct 722 ms 141192 KB Output is correct
20 Correct 687 ms 141132 KB Output is correct
21 Correct 696 ms 141136 KB Output is correct
22 Correct 689 ms 141192 KB Output is correct
23 Correct 685 ms 141164 KB Output is correct
24 Correct 688 ms 141180 KB Output is correct
25 Correct 712 ms 141096 KB Output is correct
26 Correct 730 ms 141120 KB Output is correct
27 Correct 761 ms 141188 KB Output is correct
28 Correct 713 ms 141140 KB Output is correct
29 Correct 719 ms 141164 KB Output is correct
30 Correct 784 ms 141100 KB Output is correct