Submission #581361

#	Time	Username	Problem	Language	Result	Execution time	Memory
581361		wdjpng	Wall (IOI14_wall)	C++17	0 / 100	3084 ms	13904 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;

struct s
{
    int minn = 0, maxx=1e15;
};

vector<s>T;
s def = s();
// s1 is new

int query(int i, int l, int r, int qi)
{
    if(l>qi||r<=qi) return -1;
    if(l+1==r) return i;
    return max(query(2*i,l,(l+r)/2,qi), query(2*i+1,(l+r)/2,r,qi));
}

void update(int i, int l, int r, int ui, bool add, int v)
{
    if(l>ui||r<=ui) return;
    if(l+1==r) {
        if(add) {
            T[i].minn=max(T[i].minn,v);
            T[i].maxx=max(T[i].maxx, v);
        }
        else { // cut down
            T[i].maxx=min(T[i].maxx, v); 
            T[i].minn=min(T[i].minn,v);
        }
        return;
    }

    update(2*i,l,(l+r)/2,ui,add,v);
    update(2*i+1,(l+r)/2,r,ui,add,v);
}

void buildWall(signed n, signed k, signed op[], signed left[], signed right[], signed height[], signed finalHeight[]){
    T.assign(3*n+2,s());

    rep(ck,k)
    {
        for(int i = left[ck]; i <= right[ck]; i++) update(1,0,n,i,op[ck]==1,height[ck]);
    }

    rep(i,n) finalHeight[i] = T[query(1,0,n,i)].minn;
}

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