Submission #915969

#	Time	Username	Problem	Language	Result	Execution time	Memory
915969		biank	Wall (IOI14_wall)	C++14	100 / 100	725 ms	70012 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
const int INF = 1e9;

struct Node {
    int remove, add;
    Node() : remove(INF), add(0) {}
};

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

void maxi(int &x, int h) { if(h>x) x=h; }
void mini(int &x, int h) { if(h<x) x=h; }

void compute(int u, Node h) {
    mini(st[u].remove,h.remove);
    mini(st[u].add,st[u].remove);
    maxi(st[u].add,h.add);
    maxi(st[u].remove,st[u].add);
}
    
void pass(int u) {
    if(u<SZ) {
        compute(2*u,st[u]);
        compute(2*u+1,st[u]);
        st[u]=Node();
    }
}

void update(int a, int b, Node h, int l=0, int r=SZ, int u=1) {
    pass(u);
    if(b<=l||r<=a) return;
    if(a<=l&&r<=b) return compute(u,h);
    int m=(l+r)/2;
    update(a,b,h,l,m,2*u);
    update(a,b,h,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].add;
        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(i,k) {
        Node upd;
        if(op[i]==1) upd.add=height[i];
        else upd.remove=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