제출 #337795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337795		bigDuck	벽 (IOI14_wall)	C++14	100 / 100	1598 ms	67052 KiB

wall

#include "wall.h"


#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount


pii seg[8000010];
pii nil={-1, -1};



void build(int v, int tl, int tr){

if(tl==tr){
    seg[v]=nil;
    return;
}
int mid=(tl+tr)>>1ll;

build(v*2, tl, mid); build(2*v+1, mid+1, tr);

}










void lazy(pii &sus, pii &jos){
    if(sus==nil){return;}
    if(jos==nil){jos={sus.ft, sus.sc}; sus=nil; return;}
    int hs=sus.ft, rs=sus.sc, hj=jos.ft, rj=jos.sc;

    if(rs<hj){
        jos={max(rs, hs), min(rs, rj)};
    }
    else{
        jos={max(hj, hs), min(rs, rj)};
    }
    sus=nil;
    return;
}



void update(int v, int tl, int tr, int l, int r, int tp, int x){
if(l>r){return;}
if( (tl==l) && (tr==r) ){
    pii p={0, 0};
    if(tp==1){
        p.ft=x; p.sc=100000;
    }
    else{
        p.sc=x;
    }
    lazy(p, seg[v]);
    return;
}
pii p={seg[v].ft, seg[v].sc};
lazy(seg[v], seg[v*2]), lazy(p, seg[v*2+1]);

int mid=(tl+tr)>>1ll;

update(2*v, tl, mid, l, min(r, mid), tp, x); update(2*v+1, mid+1,tr, max(l, mid+1),r, tp, x);
return;
}


int query(int v, int tl, int tr, int p){

int mid=(tl+tr)>>1ll;
if(tl==tr){
    return seg[v].ft;
}
pii pr={seg[v].ft, seg[v].sc};
lazy(seg[v], seg[v*2]), lazy(pr, seg[v*2+1]);

if(p<=mid){
    return query(2*v, tl, mid, p);
}
else{
    return query(2*v+1, mid+1, tr, p);
}

}





void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1, 1, n);
for(int i=0; i<k; i++){
    update(1, 1, n, left[i]+1, right[i]+1, op[i], height[i]);
}


for(int i=0; i<n; i++){
    finalHeight[i]=query(1, 1, n,i+1);
}



return;
}

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