oj.uz

Submission #784587

# Submission time Handle Problem Language Result Execution time Memory
784587 2023-07-16T10:29:57 Z FatihSolak Wall (IOI14_wall) C++17
100 / 100
 863 ms 151720 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;
			}
		}
		void setmin(int x){
			if(x >= maxi1)
				return;
			maxi1 = x;
			if(mini1 >= x){
				mini1 = x;
				maxi2 = -INF;
				mini2 = INF;
			}
		}		
	};
	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 260 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 1128 KB Output is correct
5 Correct 5 ms 1204 KB Output is correct
6 Correct 5 ms 1144 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 116 ms 8128 KB Output is correct
3 Correct 58 ms 4696 KB Output is correct
4 Correct 158 ms 24416 KB Output is correct
5 Correct 155 ms 24860 KB Output is correct
6 Correct 194 ms 23264 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 2 ms 340 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 111 ms 13932 KB Output is correct
9 Correct 58 ms 8524 KB Output is correct
10 Correct 149 ms 24360 KB Output is correct
11 Correct 155 ms 24836 KB Output is correct
12 Correct 172 ms 23368 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 116 ms 13900 KB Output is correct
15 Correct 28 ms 2380 KB Output is correct
16 Correct 457 ms 24304 KB Output is correct
17 Correct 303 ms 23788 KB Output is correct
18 Correct 257 ms 23804 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 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 1108 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 113 ms 13984 KB Output is correct
9 Correct 57 ms 8420 KB Output is correct
10 Correct 146 ms 24268 KB Output is correct
11 Correct 156 ms 24852 KB Output is correct
12 Correct 173 ms 23368 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 115 ms 13900 KB Output is correct
15 Correct 27 ms 2388 KB Output is correct
16 Correct 489 ms 24384 KB Output is correct
17 Correct 259 ms 23804 KB Output is correct
18 Correct 260 ms 23700 KB Output is correct
19 Correct 765 ms 151720 KB Output is correct
20 Correct 863 ms 151584 KB Output is correct
21 Correct 757 ms 151632 KB Output is correct
22 Correct 743 ms 151532 KB Output is correct
23 Correct 734 ms 151516 KB Output is correct
24 Correct 738 ms 151608 KB Output is correct
25 Correct 758 ms 151652 KB Output is correct
26 Correct 764 ms 151536 KB Output is correct
27 Correct 752 ms 151564 KB Output is correct
28 Correct 768 ms 151620 KB Output is correct
29 Correct 757 ms 151608 KB Output is correct
30 Correct 740 ms 151620 KB Output is correct