Submission #588020

#	Time	Username	Problem	Language	Result	Execution time	Memory
588020		FatihSolak	Wall (IOI14_wall)	C++17	32 / 100	500 ms	19744 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<int> st[N];
vector<int> nd[N];
struct SegTreeMAX{
	vector<int> t;
	vector<int> lazy;
	int n;
	SegTreeMAX(int size){
		n = size;
		t.assign(4*n,0);
		lazy.assign(4*n,0);
	}
	void push(int v){
		t[v*2] = max(t[v*2],lazy[v]);
		lazy[v*2] = max(lazy[v*2],lazy[v]);

		t[v*2+1] = max(t[v*2+1],lazy[v]);
		lazy[v*2+1] = max(lazy[v*2+1],lazy[v]);

		lazy[v] = 0;
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		if(tr < l || r <tl){
			return;
		}
		if(l <= tl && tr <= r){
			t[v] = max(t[v],val);
			lazy[v] = max(lazy[v],val);
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v*2+1,tm+1,tr,l,r,val);
		t[v] = max(t[v*2],t[v*2+1]);
	}
	int get(int v,int tl,int tr,int pos){
		if(tl == tr){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		if(pos <= tm){
			return get(v*2,tl,tm,pos);
		}
		else return get(v*2+1,tm+1,tr,pos);
	}
	void upd(int l,int r,int val){
		upd(1,0,n-1,l,r,val);
	}
	int get(int pos){
		return get(1,0,n-1,pos);
	}
};
struct SegTreeMIN{
	vector<int> t;
	vector<int> lazy;
	int n;
	SegTreeMIN(int size){
		n = size;
		t.assign(4*n,1e9);
		lazy.assign(4*n,1e9);
	}
	void push(int v){
		t[v*2] = min(t[v*2],lazy[v]);
		lazy[v*2] = min(lazy[v*2],lazy[v]);

		t[v*2+1] = min(t[v*2+1],lazy[v]);
		lazy[v*2+1] = min(lazy[v*2+1],lazy[v]);

		lazy[v] = 1e9;
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		if(tr < l || r <tl){
			return;
		}
		if(l <= tl && tr <= r){
			t[v] = min(t[v],val);
			lazy[v] = min(lazy[v],val);
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v*2+1,tm+1,tr,l,r,val);
		t[v] = min(t[v*2],t[v*2+1]);
	}
	int get(int v,int tl,int tr,int pos){
		if(tl == tr){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		if(pos <= tm){
			return get(v*2,tl,tm,pos);
		}
		else return get(v*2+1,tm+1,tr,pos);
	}
	void upd(int l,int r,int val){
		upd(1,0,n-1,l,r,val);
	}
	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[]){
	for(int i = 0;i<n;i++){
		finalHeight[i] = 0;
	}
	if(n <= 10000 &&  k <= 5000){
		for(int i = 0;i<k;i++){
			for(int j = left[i];j<=right[i];j++){
				if(op[i] == 1){
					finalHeight[j] = max(finalHeight[j],height[i]);
				}
				else{
					finalHeight[j] = min(finalHeight[j],height[i]);
				}
			}
		}
	}
	else{
		SegTreeMAX tmax(n);
		SegTreeMIN tmin(n);
		for(int i=0;i<k;i++){
			if(op[i] == 1){
				tmax.upd(left[i],right[i],height[i]);
			}
			else{
				tmin.upd(left[i],right[i],height[i]);
			}
		}
		for(int i = 0;i<n;i++){
			finalHeight[i] = min(tmax.get(i),tmin.get(i));
		}
	}
	return;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39