oj.uz

Submission #579012

# Submission time Handle Problem Language Result Execution time Memory
579012 2022-06-18T09:47:46 Z stevancv Wall (IOI14_wall) C++14
100 / 100
 994 ms 169680 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 4 ms 324 KB Output is correct
4 Correct 7 ms 1236 KB Output is correct
5 Correct 9 ms 1236 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 156 ms 13412 KB Output is correct
3 Correct 226 ms 8708 KB Output is correct
4 Correct 642 ms 24944 KB Output is correct
5 Correct 437 ms 26032 KB Output is correct
6 Correct 336 ms 24440 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 11 ms 1244 KB Output is correct
5 Correct 10 ms 1236 KB Output is correct
6 Correct 9 ms 1188 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 162 ms 14024 KB Output is correct
9 Correct 275 ms 8636 KB Output is correct
10 Correct 576 ms 24960 KB Output is correct
11 Correct 322 ms 26008 KB Output is correct
12 Correct 335 ms 24520 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 156 ms 13888 KB Output is correct
15 Correct 34 ms 2636 KB Output is correct
16 Correct 640 ms 25400 KB Output is correct
17 Correct 335 ms 24700 KB Output is correct
18 Correct 325 ms 24628 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 1208 KB Output is correct
5 Correct 9 ms 1236 KB Output is correct
6 Correct 9 ms 1212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 140 ms 13996 KB Output is correct
9 Correct 179 ms 8632 KB Output is correct
10 Correct 559 ms 25036 KB Output is correct
11 Correct 355 ms 26060 KB Output is correct
12 Correct 321 ms 24560 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 153 ms 13928 KB Output is correct
15 Correct 34 ms 2564 KB Output is correct
16 Correct 671 ms 25200 KB Output is correct
17 Correct 316 ms 24624 KB Output is correct
18 Correct 379 ms 24628 KB Output is correct
19 Correct 943 ms 169652 KB Output is correct
20 Correct 900 ms 167180 KB Output is correct
21 Correct 915 ms 169680 KB Output is correct
22 Correct 893 ms 167260 KB Output is correct
23 Correct 949 ms 167320 KB Output is correct
24 Correct 888 ms 167252 KB Output is correct
25 Correct 887 ms 167276 KB Output is correct
26 Correct 973 ms 169660 KB Output is correct
27 Correct 994 ms 169680 KB Output is correct
28 Correct 902 ms 167196 KB Output is correct
29 Correct 884 ms 167248 KB Output is correct
30 Correct 880 ms 167148 KB Output is correct