oj.uz

Submission #522636

# Submission time Handle Problem Language Result Execution time Memory
522636 2022-02-05T09:48:54 Z cig32 Wall (IOI14_wall) C++17
100 / 100
 886 ms 90028 KB 
#include <bits/stdc++.h>
using namespace std;
#define pi pair<int,int>
#define mi first
#define ma second
 
struct SegTree {
	vector<pi> st;//first = min, second = max
	vector<bool> marked;
	vector<int> inds;
	int sz;
	
	void init(int n){// O(n)
		sz = n;
		st.assign(4*n, {0,0});
		marked.assign(4*n, 0);
	}
	
	void calc(int n){//O(1)
		st[n].mi =min(st[2*n+1].mi, st[2*n+2].mi);
		st[n].ma =max(st[2*n+1].ma, st[2*n+2].ma);
		
		if(st[n].mi == st[n].ma)
			marked[n] = true;
	}
	
	void push(int n){//O(1)
		
		st[2*n+1].mi = st[2*n+1].ma = st[n].mi;
		st[2*n+2].mi = st[2*n+2].ma = st[n].mi;
		marked[2*n+1] = marked[2*n+2] = true;
		
		marked[n] = false;
	}
	
	void add(int n, int l, int r, int s, int e, int val){
		if(l == s && r == e && st[n].ma <= val){
			st[n].mi = st[n].ma = val;
			marked[n] = true;
		}
		else if(l == s && r == e && st[n].mi >= val){
			return;
		}
		else if(l == r){
			//cout << l<<", "<<r<<endl;
			return;
		}
			
		else{
			int mid = (l+r) /2;
			//cout << n <<", "<<st[n].ma<<": "<<l<<", "<<r<<" - "<<s<<", "<<e<<": "<<val<<endl;
			if(marked[n])
				push(n);
				
			if(s<= mid)
				add(2*n+1, l, mid, s, min(e, mid), val);
			if(e > mid)
				add(2*n+2, mid +1, r, max(s, mid+1), e, val);
			calc(n);
		}
	}
	
	void rem(int n, int l, int r, int s, int e, int val){
		if(l == s && r == e && st[n].mi >= val){
			st[n].mi = st[n].ma = val;
			marked[n] = true;
		}
		else if(l == s && r == e && st[n].ma <= val){
			return;
		}
		else if(l == r)
			return;
		else{
			//cout << n <<", "<<st[n].mi<<": "<<l<<", "<<r<<" - "<<s<<", "<<e<<": "<<val<<endl;
			int mid = (l+r) /2;
			if(marked[n])
				push(n);
				
			if(s<= mid)
				rem(2*n+1, l, mid, s, min(e, mid), val);
			if(e > mid)
				rem(2*n+2, mid +1, r, max(s, mid+1), e, val);
			calc(n);
		}
	}
	
	
	pair<int,pair<int,int>> query(int n, int l, int r, int ind){
		if(l == r)
			return {st[n].mi,{l,r}};
			
		int mid = (l+r)/2;
		if(marked[n]){
			return {st[n].mi,{l,r}};
		}
			
		if( ind <= mid)
			return query(2*n+1,l , mid, ind);
		return query(2*n+2, mid+1, r, ind);
	}
	
	void print(){
		int cnt = 0;
		
		for(int i=0; i<(int)ceil(log2(sz)); i++){
			for(int j= 0; j< (1<< i); j++)
				cout << st[cnt].mi<<", "<<st[cnt].ma<<", "<<marked[cnt]<<"\t\t",cnt++;;
				
			cout<<endl;
		}
		cout <<endl<<endl;
	}
};
 
 
void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree st;
	st.init(n);
	//st.print();
	for(int i =0;i<k;i++){
		if(op[i] == 1){
			st.add(0,1,n,left[i]+1, right[i]+1, height[i]);
		}
		else{
			st.rem(0,1,n,left[i]+1, right[i]+1, height[i]);
		}
		//st.print();
	}
	//st.print();
	
	for(int i =1; i<=n;i++){
		pair<int,pair<int,int>> res =  st.query(0,1,n,i);
		i = res.second.first;
		int end = res.second.second;
		while(i <=end){
			finalHeight[i - 1] = res.first;
			i++;
		}
		--i;
 
	}
	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 5 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 136 ms 8188 KB Output is correct
3 Correct 206 ms 4164 KB Output is correct
4 Correct 456 ms 11816 KB Output is correct
5 Correct 335 ms 11880 KB Output is correct
6 Correct 308 ms 11688 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 6 ms 716 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 133 ms 8036 KB Output is correct
9 Correct 169 ms 4184 KB Output is correct
10 Correct 540 ms 11696 KB Output is correct
11 Correct 324 ms 11644 KB Output is correct
12 Correct 286 ms 11684 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 137 ms 8024 KB Output is correct
15 Correct 33 ms 1340 KB Output is correct
16 Correct 584 ms 11688 KB Output is correct
17 Correct 273 ms 11676 KB Output is correct
18 Correct 262 ms 11624 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 129 ms 8004 KB Output is correct
9 Correct 178 ms 4164 KB Output is correct
10 Correct 474 ms 11688 KB Output is correct
11 Correct 322 ms 11688 KB Output is correct
12 Correct 312 ms 11688 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 149 ms 8020 KB Output is correct
15 Correct 48 ms 1344 KB Output is correct
16 Correct 627 ms 11692 KB Output is correct
17 Correct 283 ms 11664 KB Output is correct
18 Correct 267 ms 11740 KB Output is correct
19 Correct 733 ms 89980 KB Output is correct
20 Correct 786 ms 89944 KB Output is correct
21 Correct 762 ms 89952 KB Output is correct
22 Correct 699 ms 90028 KB Output is correct
23 Correct 716 ms 90020 KB Output is correct
24 Correct 786 ms 89972 KB Output is correct
25 Correct 814 ms 89924 KB Output is correct
26 Correct 824 ms 89896 KB Output is correct
27 Correct 718 ms 89968 KB Output is correct
28 Correct 700 ms 89888 KB Output is correct
29 Correct 886 ms 89872 KB Output is correct
30 Correct 743 ms 89988 KB Output is correct