Submission #579012

#	Time	Username	Problem	Language	Result	Execution time	Memory
579012		stevancv	Wall (IOI14_wall)	C++14	100 / 100	994 ms	169680 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e6 + 2;
int mx[4 * N], mn[4 * N], lzymn[4 * N], lzymx[4 * N], sol[N];
void Propagate(int node, int l, int r) {
    if (lzymn[node] != 1e9) {
        if (mn[node] != 1e9) smin(mn[node], lzymn[node]);
        if (l < r) {
            smin(lzymn[2 * node], lzymn[node]);
            smin(lzymn[2 * node + 1], lzymn[node]);
        }
        lzymn[node] = 1e9;
    }
    if (lzymx[node] != -1e9) {
        if (mx[node] != -1e9) smax(mx[node], lzymx[node]);
        if (l < r) {
            smax(lzymx[2 * node], lzymx[node]);
            smax(lzymx[2 * node + 1], lzymx[node]);
        }
        lzymx[node] = -1e9;
    }
}
void Walk(int node, int l, int r, int val, int op) {
    Propagate(node, l, r);
    if (op == 1 && val <= mn[node]) return;
    if (op == 2 && mx[node] <= val) return;
    if (l == r) {
        if (op == 1) sol[l] = mn[node];
        else sol[l] = mx[node];
        mx[node] = -1e9;
        mn[node] = 1e9;
        return;
    }
    int mid = l + r >> 1;
    Walk(2 * node, l, mid, val, op);
    Walk(2 * node + 1, mid + 1, r, val, op);
    mn[node] = min(mn[2 * node], mn[2 * node + 1]);
    mx[node] = max(mx[2 * node], mx[2 * node + 1]);
}
void Update(int node, int l, int r, int ql, int qr, int op, int val) {
    Propagate(node, l, r);
    if (r < ql || qr < l) return;
    if (ql <= l && r <= qr) {
        if (op == 1) smax(lzymx[node], val);
        else smin(lzymn[node], val);
        Propagate(node, l, r);
        if (mx[node] <= mn[node]) return;
        Walk(node, l, r, val, op);
        return;
    }
    int mid = l + r >> 1;
    Update(2 * node, l, mid, ql, qr, op, val);
    Update(2 * node + 1, mid + 1, r, ql, qr, op, val);
    mn[node] = min(mn[2 * node], mn[2 * node + 1]);
    mx[node] = max(mx[2 * node], mx[2 * node + 1]);
}
void FindAnswer(int node, int l, int r) {
    Propagate(node, l, r);
    if (l == r) {
        if (sol[l] == -1) sol[l] = mx[node];
        return;
    }
    int mid = l + r >> 1;
    FindAnswer(2 * node, l, mid);
    FindAnswer(2 * node + 1, mid + 1, r);
    mn[node] = min(mn[2 * node], mn[2 * node + 1]);
    mx[node] = max(mx[2 * node], mx[2 * node + 1]);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[]) {
    for (int i = 0; i < n; i++) sol[i] = -1;
    for (int i = 1; i <= 4 * n; i++) {
        mx[i] = 0; mn[i] = 1e5;
        lzymx[i] = -1e9; lzymn[i] = 1e9;
    }
    for (int i = q - 1; i >= 0; i--) {
        Update(1, 0, n - 1, l[i], r[i], op[i], h[i]);
    }
    FindAnswer(1, 0, n - 1);
    for (int i = 0; i < n; i++) {
        ans[i] = sol[i];
    }
}

Compilation message (stderr)

wall.cpp: In function 'void Walk(int, int, int, int, int)':
wall.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void Update(int, int, int, int, int, int, int)':
wall.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void FindAnswer(int, int, int)':
wall.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int mid = l + r >> 1;
      |               ~~^~~

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