제출 #810982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810982		arashMLG	벽 (IOI14_wall)	C++17	100 / 100	451 ms	107104 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

//https://quera.org/profile/4dykhk

typedef long long     ll;
typedef long double   ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N =2e6 + 23;
const int mod = 1e9+7; // 998244353
const int LOG = 23;
const ll inf = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define F           first
#define S           second
#define pb          push_back
#define ms(x,y)     memset((x) , (y) , sizeof (x))
#define done        return cout<<endl , 0;
#define kill(x)     cout<<x<<endl, exit(0);
#define isIn(x,s,e) ((x) >= (s) && (x) <= e)
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define pc(x)       __builtin_popcount(x)
#define ctz(x)      __builtin_ctz(x)
#define MinHeap(x)  priority_queue<x, vector<x> , greater<x> >
#define MaxHeap(x)  priority_queue<x, vector<x>>
#define lc          (v << 1)
#define rc          ((v<<1) |1)
//#define int      ll

ll pw(ll a, ll b, ll md = mod){ll res = 1; while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int ans[N];
pii t[N<<2];

void upd(int v,int l,int r,int x,int op,int tl,int tr) {
	if(l > r) return;
	x = max(x,t[v].F);
	x= min(x,t[v].S);
	if(l == tl && r == tr-1) {
		 if(op)
		 	t[v].S = x;
		 else
		 	t[v].F = x;
		 return;
	}
	
	int mid=(tl+tr)/2;
	
	upd(lc,l,min(mid-1,r),x,op,tl,mid);
	upd(rc,max(l,mid),r,x,op,mid,tr);
}


void make(int v,int x,int tl,int tr) {
	x = max(x,t[v].F);
	x = min(x,t[v].S);
	if(tr- tl == 1) {
		ans[tl] = x;
		return;
	}
	int mid=(tl+tr)/2;
	
	make(lc,x,tl,mid);	
	make(rc,x,mid,tr);
}


void buildWall(int n, int k, int op[], int left[], int right[], int h[], int finalHeight[]){
	for(int i = 0 ; i< (N<<2); i ++) t[i] = {0,mod};
	for(int i = k-1; i >=0 ; i--) upd(1,left[i],right[i],h[i],op[i] -1,0,n);
	make(1,0,0,n);
	for(int i = 0 ; i< n ; i++) finalHeight[i] = ans[i];
	return;
}

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