제출 #465042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465042		nkato	벽 (IOI14_wall)	C++17	100 / 100	1006 ms	99396 KiB

wall

#include "wall.h"
 
#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
 
using namespace std;
 
typedef pair<int,int> pii;
 
const int maxn=2e6+10;
pii seg[4*maxn];
int n;
 
pii comb(pii a,pii b){
    if(b==mp(-1,-1)) return a;
    pii ret=mp(min(a.xx,b.xx),max(a.yy,b.yy));
    if(ret.xx<ret.yy){
        if(ret.xx==a.xx) ret.yy=a.xx;
        else ret.xx=a.yy;
    }
    return ret;
}
 
void push(int ind){
    if(seg[ind]==mp(-1,-1)) return;
    seg[2*ind]=comb(seg[ind],seg[2*ind]);
    seg[2*ind+1]=comb(seg[ind],seg[2*ind+1]);
    seg[ind]=mp(-1,-1);
}
 
void update(int tl,int tr,int hg,int hd,int ind=1,int l=0,int r=n-1){
    if(l!=r) push(ind);
    if(tl<=l && r<=tr){
        seg[ind]=comb(mp(hg,hd),seg[ind]);
        return;
    }
    int mid=l+(r-l)/2;
    if(tl<=mid) update(tl,tr,hg,hd,2*ind,l,mid);
    if(tr>mid) update(tl,tr,hg,hd,2*ind+1,mid+1,r);
}
 
int query(int t,int ind=1,int l=0,int r=n-1){
    if(l!=r) push(ind);
    if(l==r) return seg[ind].xx;
    int mid=l+(r-l)/2;
    if(t<=mid) return query(t,2*ind,l,mid);
    if(t>mid) return query(t,2*ind+1,mid+1,r);
}
 
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N;
    for(int i=0;i<4*maxn;i++) seg[i]=mp(-1,-1);
    update(0,n-1,0,0);
    for(int i=0;i<k;i++){
        if(op[i]==1){
            update(left[i],right[i],INT_MAX,height[i]);
        }else{
            update(left[i],right[i],height[i],INT_MIN);
        }
    }
    for(int i=0;i<n;i++) finalHeight[i]=query(i);
    return;
}

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

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