Submission #349281

#	Time	Username	Problem	Language	Result	Execution time	Memory
349281		parsabahrami	Wall (IOI14_wall)	C++17	100 / 100	1040 ms	100976 KiB

wall

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 2e6 + 10;
int mx[N << 2], mn[N << 2], lz[N << 2], _n, k;

void shift(int id, int l, int r) {
    if (lz[id] < 0) return;
    mx[id] = mn[id] = lz[id];
    if (r - l > 1) {
        lz[lc] = lz[rc] = lz[id];
    }
    lz[id] = -1;
}

void setmin(int ql, int qr, int x, int id = 1, int l = 0, int r = _n) {
    shift(id, l, r);
    if (qr <= l || r <= ql || mx[id] <= x) return;
    if (ql <= l && r <= qr && mn[id] >= x) {
        lz[id] = x; 
        return shift(id, l, r);
    }  
    int mid = (l + r) >> 1;
    setmin(ql, qr, x, lc, l, mid);
    setmin(ql, qr, x, rc, mid, r);
    mn[id] = min(mn[lc], mn[rc]);
    mx[id] = max(mx[lc], mx[rc]);
}

void setmax(int ql, int qr, int x, int id = 1, int l = 0, int r = _n) {
    shift(id, l, r);
    if (qr <= l || r <= ql || mn[id] >= x) return;
    if (ql <= l && r <= qr && mx[id] <= x) {
        lz[id] = x; 
        return shift(id, l, r);
    }  
    int mid = (l + r) >> 1;
    setmax(ql, qr, x, lc, l, mid);
    setmax(ql, qr, x, rc, mid, r);
    mn[id] = min(mn[lc], mn[rc]);
    mx[id] = max(mx[lc], mx[rc]);
}

int print(int pos, int id = 1, int l = 0, int r = _n) {
    shift(id, l, r);
    if (r - l < 2) {
        return mx[id];
    }
    int mid = (l + r) >> 1;
    if (pos < mid) return print(pos, lc, l, mid);
    else return print(pos, rc, mid, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	memset(lz, -1, sizeof lz);
    _n = n;
    for (int i = 0; i < k; i++) {
        int t = op[i], l = left[i], r = right[i], h = height[i];
        if (t == 1) setmax(l, r + 1, h);
        else setmin(l, r + 1, h);
    }
    for (int i = 0; i < n; i++) finalHeight[i] = print(i);
    return;
}

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