Submission #252471

#	Time	Username	Problem	Language	Result	Execution time	Memory
252471		eohomegrownapps	Wall (IOI14_wall)	C++14	100 / 100	2980 ms	204804 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

//segment tree, rmaxq

struct Node{
    int s,e,m,v=0;
    Node *l, *r;
    Node(int _s, int _e){
        s=_s;e=_e;
        if (s==e){
            return;
        }
        m=(s+e)/2;
        l = new Node(s,m);
        r = new Node(m+1,e);
    }
    void update(int ind, int val){
        //cout<<"upd "<<ind<<" "<<val<<'\n';
        if (s==e){
            v=val;
            return;
        }
        if (ind<=m){
            l->update(ind,val);
        } else {
            r->update(ind,val);
        }
        v=max(l->v,r->v);
    }
    int query(int a, int b){
        if (s==a&&e==b){
            return v;
        }
        if (b<=m){
            return l->query(a,b);
        } else if (m<a){
            return r->query(a,b);
        } else {
            return max(l->query(a,m),r->query(m+1,b));
        }
    }
};

Node *radd;
Node *rrem;
int MX = 100001;
int n,k;
bool success(int x){
    if (x==k){return true;}
    return (radd->query(x,k-1)+rrem->query(x,k-1))<=MX;
}

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N;k=K;
    vector<pair<int,pair<int,bool>>> ptrs[2000000]; 
    int kadd[500000];
    //{time,{height,add/rem}}
    for (int i = 0; i<k; i++){
        bool phase = (op[i]-1);
        int h = height[i];
        int l = left[i];
        int r = right[i];
        if (phase){
            h=MX-h;
        }
        ptrs[l].push_back({i,{h,phase}});
        if (r!=n-1){
            ptrs[r+1].push_back({i,{0,phase}});
        }
        kadd[i]=0;
    }
    radd=new Node(0,k-1);
    rrem=new Node(0,k-1);
    int prevval = 0;
    for (int x = 0; x<n; x++){
        //cout<<x<<":\n";
        //process x
        if (ptrs[x].size()==0){
            finalHeight[x]=prevval;
            //cout<<prevval<<'\n';
            continue;
        }
        for (auto i : ptrs[x]){
            int time = i.first;
            int h = i.second.first;
            int isRem = i.second.second;
            if (isRem){
                rrem->update(time,h);
            } else {
                radd->update(time,h);
                kadd[time]=h;
            }
        }
        int l = 0, r = k-1;
        while (l<=r){
            int mid = (l+r)/2;
            //cout<<mid<<'\n';
            if (success(mid)){
                r=mid-1;
            } else {
                l=mid+1;
            }
        }
        //cout<<"bleh\n";
        if (l==0){
            //there is no overlap
            finalHeight[x] = radd->query(0,k-1);
        } else {
            //there is overlap
            int lastind = l-1;
            int addafter = radd->query(lastind,k-1);
            int remafter = rrem->query(lastind,k-1);
            int addval = kadd[lastind];
            if (addval+remafter>MX){
                //remove is after
                finalHeight[x]=MX-remafter;
            } else {
                //add is after
                finalHeight[x]=addafter;
            }
        }
        prevval=finalHeight[x];
        //cout<<prevval<<'\n';
    }
}

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