제출 #902219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
902219		Sir_Ahmed_Imran	벽 (IOI14_wall)	C++17	8 / 100	3096 ms	20092 KiB

wall

                              ///~~~LOTA~~~///
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define LIMIT 50000001 
#define MAXN 100000
int L[4*MAXN];
int R[4*MAXN];
int ANS[MAXN];
void get(int l=0,int r=MAXN,int v=1,int s=0,int e=MAXN){
    l=max(l,L[v]);
    r=min(r,R[v]);
    if(e-s==1){
        ANS[s]=min(l,r);
        return;
    }
    int lc,rc,mid;
    lc=2*v;
    rc=2*v+1;
    mid=(s+e)/2;
    get(l,r,lc,s,mid);
    get(l,r,rc,mid,e);
}
void update(int l,int r,int x,int i,int v=1,int s=0,int e=MAXN){
    if(r<=s || e<=l || s>=e) return;
    if(l<=s && e<=r){
        if(i==1) L[v]=max(L[v],x);
        else R[v]=min(R[v],x); 
        return;
    }
    int lc,rc,mid;
    lc=2*v;
    rc=2*v+1;
    mid=(s+e)/2;
    update(l,r,x,i,lc,s,mid);
    update(l,r,x,i,rc,mid,e);
}
void buildWall(int n,int m,int t[],int l[],int r[],int h[],int ans[]){
    for(int i=0;i<4*MAXN;i++)
        R[i]=MAXN;
    for(int i=0;i<m;i++){
        if(n*m<LIMIT){
            for(int j=l[i];j<=r[i];j++){
                if(t[i]==1) ANS[j]=max(ANS[j],h[i]);
                else ANS[j]=min(ANS[j],h[i]);
            }
        }
        else update(l[i],r[i]+1,h[i],t[i]);
    }
    if(n*m>=LIMIT) get();
    for(int i=0;i<n;i++) ans[i]=ANS[i];
}

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