Submission #1097053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097053		vjudge1	Wall (IOI14_wall)	C++17	100 / 100	605 ms	69476 KiB

wall

#include<bits/stdc++.h>
using namespace std;
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) forsn(i,0,n)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) dforsn(i,0,n)
#define sz(x) int(x.size())
#define all(x) begin(x),end(x)
#define pb push_back
#define fst first
#define snd second

const int INF=1e9;

typedef pair<int,int> ii;

const int SZ=1<<21;
ii st[2*SZ];

template<typename T> void chmax(T &x, T v){ if(v>x) x=v; }
template<typename T> void chmin(T &x, T v){ if(v<x) x=v; }

ii &operator+=(ii &a, ii b){
    chmin(a.fst,b.fst);
    chmin(a.snd,a.fst);
    chmax(a.snd,b.snd);
    chmax(a.fst,a.snd);
    return a;
}
    
void pass(int u) {
    if(u<SZ){
        st[2*u]+=st[u],st[2*u+1]+=st[u];
        st[u]={INF,0};
    }
}

void update(int s, int e, ii v, int l=0, int r=SZ, int u=1){
    pass(u);
    if(e<=l||r<=s) return;
    if(s<=l&&r<=e){
        st[u]+=v;
        return;
    }
    int m=(l+r)/2;
    update(s,e,v,l,m,2*u);
    update(s,e,v,m,r,2*u+1);
}

void dfs(int ans[], int n, int l=0, int r=SZ, int u=1){
    pass(u);
    if(r-l==1){
        if(l<n) ans[l]=st[u].snd;
        return;
    }
    int m=(l+r)/2;
    dfs(ans,n,l,m,2*u);
    dfs(ans,n,m,r,2*u+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    forn(u,2*SZ) st[u]={INF,0};
    forn(i,k){
        ii upd={INF,0};
        if(op[i]==1) upd.snd=height[i];
        else upd.fst=height[i];
        update(left[i],right[i]+1,upd);
    }
    dfs(finalHeight,n);
}

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