제출 #409457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409457		dreezy	Wall (IOI14_wall)	C++17	8 / 100	3073 ms	8084 KiB

wall

#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){
		sz = n;
		st.assign(4*n, {0,0});
		marked.assign(4*n, 0);
	}
	
	void calc(int n){
		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){
		
		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 == 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 == 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 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39