Submission #1030979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030979		ArthuroWich	Wall (IOI14_wall)	C++17	100 / 100	711 ms	86868 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int segmin[4*2000005], segmax[4*2000005], lazy[4*2000005];
void lazypropagate(int n, int l, int r) {
    if (lazy[n] != -1) {
        segmin[n] = lazy[n];
        segmax[n] = lazy[n];
        if (l != r) {
            lazy[2*n] = lazy[n];
            lazy[2*n+1] = lazy[n];
        }
        lazy[n] = -1;
    }
}
void update1(int n, int l, int r, int a, int b, int h) {
    lazypropagate(n, l, r);
    if (b < l || r < a || segmin[n] >= h) {
        return;
    }
    if (a <= l && r <= b && segmax[n] < h) {
        lazy[n] = h;
        lazypropagate(n, l, r);
    } else { 
        int m = (l+r)/2;
        update1(2*n, l, m, a, b, h);
        update1(2*n+1, m+1, r, a, b, h);
        segmax[n] = max(segmax[2*n], segmax[2*n+1]);
        segmin[n] = min(segmin[2*n], segmin[2*n+1]);
    }
}
void update2(int n, int l, int r, int a, int b, int h) {
    lazypropagate(n, l, r);
    if (b < l || r < a || segmax[n] <= h) {
        return;
    }
    if (a <= l && r <= b && segmin[n] > h) {
        lazy[n] = h;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        update2(2*n, l, m, a, b, h);
        update2(2*n+1, m+1, r, a, b, h);
        segmax[n] = max(segmax[2*n], segmax[2*n+1]);
        segmin[n] = min(segmin[2*n], segmin[2*n+1]);
    }
}
int query(int n, int l, int r, int i) {
    lazypropagate(n, l, r);
    if (l == r) {
        return segmax[n];
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            return query(2*n, l, m, i);
        } else {
            return query(2*n+1, m+1, r, i);
        }
    }
} 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            update1(1, 0, n-1, left[i], right[i], height[i]);
        } else {
            update2(1, 0, n-1, left[i], right[i], height[i]);
        }
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = query(1, 0, n-1, i);
    }
    return;
}

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