Submission #52148

#	Time	Username	Problem	Language	Result	Execution time	Memory
52148		aquablitz11	Wall (IOI14_wall)	C++14	100 / 100	942 ms	59580 KiB

wall

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

const int N = 1<<21;
const int INF = 1e9;

int n, lo[N<<1], hi[N<<1], *ans;

void addtag(int p, int c, int d)
{
    int a = lo[p], b = hi[p];
    lo[p] = min(d, max(a, c));
    hi[p] = max(c, min(b, d));
}

void push(int p, int b, int e)
{
    if (b == e) {
        ans[b] = min(max(ans[b], lo[p]), hi[p]);
    } else {
        int m = (b+e)/2;
        addtag(p<<1, lo[p], hi[p]);
        addtag(p<<1|1, lo[p], hi[p]);
    }
    lo[p] = 0;
    hi[p] = INF;
}

void build(int p=1, int b=0, int e=n-1)
{
    hi[p] = INF;
    if (b == e)
        return;
    int m = (b+e)/2;
    build(p<<1, b, m);
    build(p<<1|1, m+1, e);
}

void update(int l, int r, int x, int y, int p=1, int b=0, int e=n-1)
{
    if (e < l || b > r)
        return;
    if (b >= l && e <= r) {
        addtag(p, x, y);
    } else {
        push(p, b, e);
        int m = (b+e)/2;
        update(l, r, x, y, p<<1, b, m);
        update(l, r, x, y, p<<1|1, m+1, e);
    }
}

void finish(int p=1, int b=0, int e=n-1)
{
    push(p, b, e);
    if (b == e)
        return;
    int m = (b+e)/2;
    finish(p<<1, b, m);
    finish(p<<1|1, m+1, e);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    ::n = n;
    ans = finalHeight;
    build();
    for (int i = 0; i < k; ++i) {
        if (op[i] == 1)
            update(left[i], right[i], height[i], INF);
        else
            update(left[i], right[i], 0, height[i]);
    }
    finish();

    return;
}

Compilation message (stderr)

wall.cpp: In function 'void push(int, int, int)':
wall.cpp:22:13: warning: unused variable 'm' [-Wunused-variable]
         int m = (b+e)/2;
             ^

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