제출 #432064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432064		REALITYNB	벽 (IOI14_wall)	C++17	61 / 100	3012 ms	155316 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
const int mxn = 1e7 , N =2e6+500 ;
vector<vector<int>> sg(2,vector<int>(mxn,-1));
int query(int t ,int in,int l ,int r ,int ql ,int qr){
    if(qr<l||r<ql) return -1 ;
    if(ql<=l&&r<=qr) return sg[t][in] ;
    int ans = query(t,in*2,l,(r+l)/2,ql,qr);
    ans=max(ans,query(t,in*2+1,(r+l)/2+1,r,ql,qr)) ;
    return ans;
}
int query(int i ,int t){
    if(t) i=N-i;
    return query(t,1,0,N,0,i);
}
void update(int t , int in, int l ,int r , int i,int v){
    if(i<l||r<i) return ;
    if(l==i&&r==i){
        sg[t][in]=v ;
        return ;
    }
    update(t,in*2,l,(r+l)/2,i,v);
    update(t,in*2+1,(l+r)/2+1,r,i,v);
    sg[t][in]=max(sg[t][in*2],sg[t][in*2+1]) ;
    //return sg[t][in] ;
}
void update(int i , int v , int t){
    if(t) i=N-i;
    update(t,1,0,N,i,v) ;
    return ;
}
void buildWall(int n,int k,int op[],int le[],int re[],int he[],int* ans){
    vector<vector<array<int,3>>> in(n) , out(n);
    set<int> ok ;
    for(int i=0;i<k;i++){
        if(op[i]==2) op[i]=0;
    }
    for(int i=0;i<k;i++) ok.insert(he[i]) ;
    ok.insert(0);
    int cnt =1;
    map<int,int> ki ,rk ;
    for(int x:ok) ki[x]=++cnt,rk[cnt]=x;
    for(int i=0;i<k;i++){
        in[le[i]].pb({op[i],ki[he[i]],i}) ;
        out[re[i]].pb({op[i],ki[he[i]],i});
    }
    set<int> hey[2][cnt+1];
    for(int i=0;i<n;i++){
        for(auto x  : in[i]){
            int t = x[0] , he = x[1],tim=x[2] ;
            hey[t][he].insert(tim) ;
            tim = *(--hey[t][he].end()) ;
            update(he,tim,t) ;
        }
        int l=1,r=cnt+1;
        while(r-l!=1){
            int md=(r+l)/2 ;
            int val = query(md-1,0) ,vall = query(md,1) ;
            if(vall>val) l=md ;
            else r=md;
        }
        ans[i]=rk[l];
        for(auto x: out[i]){
            int t=x[0],he=x[1],tim=x[2];
            hey[t][he].erase(tim) ;
            update(he,-1,t);
            if(hey[t][he].size()){
                update(he,*(--hey[t][he].end()),t);
            }
        }
    }
    return ;
}

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