Submission #93939

#	Time	Username	Problem	Language	Result	Execution time	Memory
93939		Alexa2001	Wall (IOI14_wall)	C++17	100 / 100	637 ms	69496 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

const int lim = 1e5, Nmax = 2e6 + 5;

class SegTree
{
    int a[Nmax<<2], b[Nmax<<2];

    void combine(int node, int x, int y)
    {
        if(b[node] <= x) a[node] = b[node] = x;
            else if(a[node] >= y) a[node] = b[node] = y;
                else a[node] = max(a[node], x), b[node] = min(b[node], y);
    }

    void propag(int node)
    {
        combine(left_son, a[node], b[node]);
        combine(right_son, a[node], b[node]);
        a[node] = 0; b[node] = lim;
    }

public:
    void update(int node, int st, int dr, int L, int R, int A, int B)
    {
        if(L <= st && dr <= R)
        {
            combine(node, A, B);
            return;
        }

        propag(node);

        if(L <= mid) update(left_son, st, mid, L, R, A, B);
        if(mid < R) update(right_son, mid+1, dr, L, R, A, B);
    }

    void propag(int node, int st, int dr, int *Ans)
    {
        if(st == dr)
        {
            Ans[st] = a[node];
            return;
        }
        propag(node);
        propag(left_son, st, mid, Ans);
        propag(right_son, mid+1, dr, Ans);
    }

    void init(int node, int st, int dr)
    {
        a[node] = 0, b[node] = lim;
        if(st == dr) return;
        init(left_son, st, mid); init(right_son, mid+1, dr);
    }
} aint;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    aint.init(1, 0, n-1);
    int i;
    for(i=0; i<k; ++i)
        aint.update(1, 0, n-1, left[i], right[i], (op[i] == 1 ? height[i] : 0), (op[i] == 1 ? lim : height[i]));

    aint.propag(1, 0, n-1, finalHeight);
}

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