Submission #409431

#	Time	Username	Problem	Language	Result	Execution time	Memory
409431		MDario	Wall (IOI14_wall)	C++11	100 / 100	1010 ms	107124 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
pair<int, int> st[8000001];
int r[2000001];
void lazy(ll xf, ll lf, ll rf){
    if(lf==rf)return;
    st[xf*2].F=min(st[xf*2].F, st[xf].S);
    st[xf*2].F=max(st[xf*2].F, st[xf].F);
    st[xf*2].S=max(st[xf*2].F, min(st[xf*2].S, st[xf].S));
    st[xf*2+1].F=min(st[xf*2+1].F, st[xf].S);
    st[xf*2+1].F=max(st[xf*2+1].F, st[xf].F);
    st[xf*2+1].S=max(st[xf*2+1].F, min(st[xf*2+1].S, st[xf].S));
    st[xf]={0, 1000000};
    return;
}
void update1(int xf, int lf, int rf, int ol, int od, int v){
    lazy(xf, lf, rf);
    if(rf<ol||lf>od)return;
    if(ol<=lf&&rf<=od){
        if(lf==rf){
            st[xf].F=max(st[xf].F, v);
            st[xf].S=max(st[xf].S, v);
            return;
        }
        st[xf].F=v;
        lazy(xf, lf, rf);
        return;
    }
    update1(xf*2, lf, (lf+rf)/2, ol, od, v);
    update1(xf*2+1, (lf+rf)/2+1, rf, ol, od, v);
    return ;
}
void update2(int xf, int lf, int rf, int ol, int od, int v){
    lazy(xf, lf, rf);
    if(rf<ol||lf>od)return;
    if(ol<=lf&&rf<=od){
        if(lf==rf){
            st[xf].F=min(st[xf].F, v);
            st[xf].S=min(st[xf].S, v);
            return;
        }
        st[xf].S=v;
        lazy(xf, lf, rf);
        return;
    }
    update2(xf*2, lf, (lf+rf)/2, ol, od, v);
    update2(xf*2+1, (lf+rf)/2+1, rf, ol, od, v);
    return ;
}
void rbuild(int xf, int lf, int rf){
    lazy(xf, lf, rf);
    if(lf==rf){
        r[lf]=st[xf].F;
        return;
    }
    rbuild(xf*2, lf, (lf+rf)/2);
    rbuild(xf*2+1, (lf+rf)/2+1, rf);
    return ;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=0; i<=4*n; i++)st[i].S=1000000;
    for(int i=0; i<k; i++){
        if(op[i]==1)update1(1, 1, n, left[i]+1, right[i]+1, height[i]);
        else update2(1, 1, n, left[i]+1, right[i]+1, height[i]);
    }
    rbuild(1, 1, n);
    for(int i=0; i<n; i++){
        finalHeight[i]=r[i+1];
    }
    return;
}

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