제출 #1076965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1076965		asli_bg	벽 (IOI14_wall)	C++11	100 / 100	636 ms	161948 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
 
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
 
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
 
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi sp el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PDEBUG(X) { cout << #X << " = " << (X.fi) sp (X.se) << endl; }
 
#define carp(x,y) ((x%mod)*(y%mod))%mod
#define topla(x,y) ((x%mod)+(y%mod))%mod
 
const int MAXN=2e6+3;
const int INF=1e9;
const int mod=1e9+7;
 
#define mid (l+r)/2
#define endl '\n'

struct dug{
    int bir;
    int t1;
    int iki;
    int t2;
};

int n;

dug t[4*MAXN];
vi a;
int say;

void push(int nd,int l,int r){
    if(t[nd].bir==0 and t[nd].iki==INF) return;

    if(t[nd*2].bir<t[nd].bir){
        t[nd*2].bir=t[nd].bir;
        t[nd*2].t1=t[nd].t1;
    }
    if(t[nd*2].iki>t[nd].iki){
        t[nd*2].iki=t[nd].iki;
        t[nd*2].t2=t[nd].t2;
    }
    if(t[nd*2].bir>t[nd*2].iki){
        if(t[nd*2].t1>t[nd*2].t2){
            t[nd*2].iki=t[nd*2].bir;
            t[nd*2].t2=t[nd*2].t1;
        }
        else{
            t[nd*2].bir=t[nd*2].iki;
            t[nd*2].t1=t[nd*2].t2;
        }
    }
    ////////////////////////////////////////
    if(t[nd*2+1].bir<t[nd].bir){
        t[nd*2+1].bir=t[nd].bir;
        t[nd*2+1].t1=t[nd].t1;
    }
    if(t[nd*2+1].iki>t[nd].iki){
        t[nd*2+1].iki=t[nd].iki;
        t[nd*2+1].t2=t[nd].t2;
    }
    if(t[nd*2+1].bir>t[nd*2+1].iki){
        if(t[nd*2+1].t1>t[nd*2+1].t2){
            t[nd*2+1].iki=t[nd*2+1].bir;
            t[nd*2+1].t2=t[nd*2+1].t1;
        }
        else{
            t[nd*2+1].bir=t[nd*2+1].iki;
            t[nd*2+1].t1=t[nd*2+1].t2;
        }
    }

    t[nd].bir=t[nd].t1=t[nd].t2=0;
    t[nd].iki=INF;
}

int query(int pos,int nd=1,int l=1,int r=n){
    if(l==r){
        if(t[nd].bir<t[nd].iki) return t[nd].bir;
        if(t[nd].t1>t[nd].t2) return t[nd].bir;
        else return t[nd].iki;
    }
    push(nd,l,r);
    if(pos<=mid) return query(pos,nd*2,l,mid);
    else return query(pos,nd*2+1,mid+1,r);
}

void update(int ql,int qr,int h,bool f,int nd=1,int l=1,int r=n){
    if(l>r or l>qr or r<ql) return;
    if(ql<=l and r<=qr){
        if(f){ //dik
            if(t[nd].bir<h){
                t[nd].bir=h;
                t[nd].t1=say;
                if(t[nd].iki!=INF and t[nd].bir>t[nd].iki){
                    t[nd].iki=t[nd].bir;
                    t[nd].t2=t[nd].t1;
                }
            }
        }
        else{ //yık
            if(t[nd].iki>h){
                t[nd].iki=h;
                t[nd].t2=say;
                if(t[nd].bir!=0 and t[nd].iki<t[nd].bir){
                    t[nd].bir=t[nd].iki;
                    t[nd].t1=t[nd].t2;
                }
            }
        }
        return;
    }
    push(nd,l,r);
    update(ql,qr,h,f,nd*2,l,mid);
    update(ql,qr,h,f,nd*2+1,mid+1,r);
}

void buildWall(int sz, int m, int opp[], int left[], int right[], int height[], int cev[]){
    n=sz;
    FOR(i,4*sz+1){
        t[i].bir=t[i].t1=t[i].t2=0;
        t[i].iki=INF;
    }

    say=1;
    FOR(i,m){
        int op=opp[i];
        int l=left[i];
        int r=right[i];
        int h=height[i];
        l++;r++;
        if(op==1){
            update(l,r,h,1);
        }
        else{
            update(l,r,h,0);
        }
        say++;
    }

    FORE(i,1,sz+1){
        cev[i-1]=query(i);
    }
    
    return;
}

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