제출 #554399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554399		Koosha_mv	벽 (IOI14_wall)	C++14	100 / 100	1090 ms	124692 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#include "wall.h"

const int N=2e6+99;

int n,m,q,mx0,mx1;
int ans[N],seg[2][N];
vector<pair<int,int>> A;
vector<pair<int,pair<int,int>>> vec[N];

void upd(int x,int val,int s,int id=1,int l=0,int r=m){
	if(r<=x || x<l) return ;
	if(l+1==r){
		seg[s][id]=val;
		return ;
	}
	int mid=(l+r)>>1;
	upd(x,val,s,id<<1,l,mid);
	upd(x,val,s,id<<1|1,mid,r);
	seg[s][id]=max(seg[s][id<<1],seg[s][id<<1|1]);
}
int get(int id=1,int l=0,int r=m){
	if(l+1==r){
		//eror(l);
		return A[l].F;
	}
	int mid=(l+r)>>1;
	//eror(mx1);
	//cout<<(id<<1|1)<<" - "<<seg[1][id<<1|1]<<endl;
	if(max(mx0,seg[0][id<<1])>=max(mx1,seg[1][id<<1|1])){
		maxm(mx1,seg[1][id<<1|1]);
		return get(id<<1,l,mid);
	}
	maxm(mx0,seg[0][id<<1]);
	return get(id<<1|1,mid,r);
}
void buildWall(int _n,int _k,int op[],int left[],int right[],int height[],int finalHeight[]){
	n=_n;
	q=_k;
	f(i,0,q) A.pb({height[i],i}),right[i]++,op[i]=2-op[i];
	A.pb({0,-1});
	sort(all(A));
	//for(auto p : A) erorp(p);
	f(i,0,q){
		int x=lower_bound(all(A),mp(height[i],i))-A.begin();
		vec[left[i]].pb({op[i],{x,i+1}});
		vec[right[i]].pb({op[i],{x,0}});
	}
	m=A.size();
	f(i,0,n){
		//cout<<"step "<<i<<endl;
		for(auto p : vec[i]){
			//cout<<p.S.F<<" "<<p.S.S<<" "<<p.F<<endl;
			upd(p.S.F,p.S.S,p.F);
		}
		mx0=mx1=0;
		ans[i]=get();
		//return ;
	}
	//dbga(ans,0,n);
	f(i,0,n) finalHeight[i]=ans[i];
}

/*
4
1
1 1 2 10

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n,q,l[100],r[100],op[100],h[100],p[100];
	cin>>n>>q;
	f(i,0,q) cin>>op[i]>>l[i]>>r[i]>>h[i];
	buildWall(n,q,op,l,r,h,p);
}*/

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