Submission #92511

#	Time	Username	Problem	Language	Result	Execution time	Memory
92511		easrui	Wall (IOI14_wall)	C++14	100 / 100	649 ms	77304 KiB

wall

#include <bits/stdc++.h>
#define vl first
#define vr second
//#include "wall.h"
using namespace std;
typedef pair<int,int> pii;
const int MN = 2e6+5;

pii ST[4*MN];
int finH[MN];

void init(int s, int e, int pos)
{
    ST[pos].vl = 0;
    ST[pos].vr = MN;
    if(s==e) return;
    int m = (s+e)/2;
    init(s,m,2*pos);
    init(m+1,e,2*pos+1);
}

void fin(int s, int e, int pos)
{
    int L = ST[pos].vl, R = ST[pos].vr;
    if(s==e){
        finH[s] = L;
        return;
    }
    int m = (s+e)/2;
    ST[2*pos].vl = max(ST[2*pos].vl,L);
    ST[2*pos].vr = max(ST[2*pos].vr,L);
    ST[2*pos].vl = min(ST[2*pos].vl,R);
    ST[2*pos].vr = min(ST[2*pos].vr,R);
    ST[2*pos+1].vl = max(ST[2*pos+1].vl,L);
    ST[2*pos+1].vr = max(ST[2*pos+1].vr,L);
    ST[2*pos+1].vl = min(ST[2*pos+1].vl,R);
    ST[2*pos+1].vr = min(ST[2*pos+1].vr,R);
    fin(s, m, 2*pos);
    fin(m+1, e, 2*pos+1);
}

void upt(int qu, int l, int r, int h, int s, int e, int pos)
{
    if(e<l || s>r) return;
    int L = ST[pos].vl, R = ST[pos].vr;
    if(l<=s && e<=r){
        if(qu==1){
            ST[pos].vl = max(L,h);
            ST[pos].vr = max(R,h);
        }
        else{
            ST[pos].vl = min(L,h);
            ST[pos].vr = min(R,h);
        }
        return ;
    }
    int m = (s+e)/2;
    ST[2*pos].vl = max(ST[2*pos].vl,L);
    ST[2*pos].vr = max(ST[2*pos].vr,L);
    ST[2*pos].vl = min(ST[2*pos].vl,R);
    ST[2*pos].vr = min(ST[2*pos].vr,R);
    ST[2*pos+1].vl = max(ST[2*pos+1].vl,L);
    ST[2*pos+1].vr = max(ST[2*pos+1].vr,L);
    ST[2*pos+1].vl = min(ST[2*pos+1].vl,R);
    ST[2*pos+1].vr = min(ST[2*pos+1].vr,R);
    ST[pos].vl = 0;
    ST[pos].vr = MN;
    upt(qu, l, r, h, s, m, 2*pos);
    upt(qu, l, r, h, m+1, e, 2*pos+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    init(0,n-1,1);
    //cout << height[0] << '\n';
    for(int i=0; i<k; i++) upt(op[i],left[i],right[i],height[i],0,n-1,1);
    //cout << 1 << '\n';
    fin(0,n-1,1);
    for(int i=0; i<n; i++) finalHeight[i] = finH[i];
};

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