oj.uz

Submission #409458

# Submission time Handle Problem Language Result Execution time Memory
409458 2021-05-20T19:21:48 Z dreezy Wall (IOI14_wall) C++17
100 / 100
 931 ms 82840 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;

	}
	
}


/*int main(){
	int n, k;
	cin >> n >> k;
	
	int op[n], left[n], right[n], height[n], finalHeight[n];
	
	for(int i =0; i<k;i++){
		cin >> op[i]>>left[i]>>right[i]>>height[i];
	}
	
	buildWall(n, k, op, left,right,height,finalHeight);
	
	for(int i =0; i<n;i++){
		cout << finalHeight[i]<<endl;
	}
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 8 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 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 152 ms 8052 KB Output is correct
3 Correct 218 ms 4292 KB Output is correct
4 Correct 624 ms 14852 KB Output is correct
5 Correct 421 ms 14788 KB Output is correct
6 Correct 394 ms 14828 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 8 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 152 ms 8164 KB Output is correct
9 Correct 214 ms 4160 KB Output is correct
10 Correct 619 ms 14820 KB Output is correct
11 Correct 423 ms 14916 KB Output is correct
12 Correct 389 ms 14916 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 159 ms 11316 KB Output is correct
15 Correct 43 ms 1900 KB Output is correct
16 Correct 747 ms 14948 KB Output is correct
17 Correct 343 ms 14916 KB Output is correct
18 Correct 337 ms 14964 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 155 ms 8116 KB Output is correct
9 Correct 217 ms 4164 KB Output is correct
10 Correct 622 ms 14952 KB Output is correct
11 Correct 420 ms 14788 KB Output is correct
12 Correct 392 ms 14788 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 159 ms 11256 KB Output is correct
15 Correct 44 ms 1880 KB Output is correct
16 Correct 733 ms 14888 KB Output is correct
17 Correct 339 ms 14888 KB Output is correct
18 Correct 339 ms 14896 KB Output is correct
19 Correct 925 ms 82704 KB Output is correct
20 Correct 915 ms 82672 KB Output is correct
21 Correct 916 ms 82744 KB Output is correct
22 Correct 916 ms 82796 KB Output is correct
23 Correct 901 ms 82840 KB Output is correct
24 Correct 908 ms 82740 KB Output is correct
25 Correct 906 ms 82748 KB Output is correct
26 Correct 915 ms 82676 KB Output is correct
27 Correct 921 ms 82672 KB Output is correct
28 Correct 929 ms 82572 KB Output is correct
29 Correct 908 ms 82636 KB Output is correct
30 Correct 931 ms 82484 KB Output is correct