oj.uz

Submission #831336

# Submission time Handle Problem Language Result Execution time Memory
831336 2023-08-20T06:03:19 Z chanhchuong123 Wall (IOI14_wall) C++14
100 / 100
 508 ms 69524 KB 
#include <wall.h>
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;
const int MAX = 2000020;
int n, k;
pair<int, int> st[(1 << 22) + 5];

void build(int id, int l, int r) {
    st[id] = make_pair(+INF, -INF);
    if (l == r) {
        st[id] = make_pair(+INF, 0);
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

void pushMax(int id, int h) {
    st[id].first = max(st[id].first, h); st[id].second = max(st[id].second, h);
}
void pushMin(int id, int h) {
    st[id].first = min(st[id].first, h); st[id].second = min(st[id].second, h);
}
void push(int id) {
    if (st[id].first != +INF) {
        pushMin(id << 1, st[id].first);
        pushMin(id << 1 | 1, st[id].first);
    }
    if (st[id].second != -INF) {
        pushMax(id << 1, st[id].second);
        pushMax(id << 1 | 1, st[id].second);
    }
    st[id] = make_pair(+INF, -INF);
}

void update(int id, int l, int r, int u, int v, int h, int t) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        if (!t) pushMax(id, h);
        else pushMin(id, h);
        return;
    }
    push(id);
    int mid = l + r >> 1;
    update(id << 1, l, mid, u, v, h, t);
    update(id << 1 | 1, mid + 1, r, u, v, h, t);
}

void getAns(int id, int l, int r, int ans[]) {
    if (l == r) ans[l] = st[id].second;
    else {
        push(id);
        int mid = l + r >> 1;
        getAns(id << 1, l, mid, ans);
        getAns(id << 1 | 1, mid + 1, r, ans);
    }
}

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    n = N, k = K;
    build(1, 0, n - 1);
    for (int i = 0; i < k; ++i) {
        update(1, 0, n - 1, left[i], right[i], height[i], op[i] - 1);
    }
    getAns(1, 0, n - 1, finalHeight);
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void getAns(int, int, int, int*)':
wall.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 1 ms 372 KB Output is correct
4 Correct 4 ms 764 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 704 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 101 ms 13820 KB Output is correct
3 Correct 112 ms 7908 KB Output is correct
4 Correct 340 ms 20304 KB Output is correct
5 Correct 207 ms 21452 KB Output is correct
6 Correct 189 ms 19816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 3 ms 704 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 100 ms 13836 KB Output is correct
9 Correct 113 ms 7908 KB Output is correct
10 Correct 324 ms 20312 KB Output is correct
11 Correct 188 ms 21360 KB Output is correct
12 Correct 184 ms 19848 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 135 ms 13848 KB Output is correct
15 Correct 21 ms 2000 KB Output is correct
16 Correct 357 ms 20568 KB Output is correct
17 Correct 201 ms 20072 KB Output is correct
18 Correct 186 ms 20032 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 368 KB Output is correct
4 Correct 4 ms 764 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 772 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 108 ms 13968 KB Output is correct
9 Correct 114 ms 7912 KB Output is correct
10 Correct 308 ms 20312 KB Output is correct
11 Correct 190 ms 21416 KB Output is correct
12 Correct 180 ms 19840 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 101 ms 13940 KB Output is correct
15 Correct 21 ms 2012 KB Output is correct
16 Correct 371 ms 20624 KB Output is correct
17 Correct 186 ms 20012 KB Output is correct
18 Correct 189 ms 20056 KB Output is correct
19 Correct 508 ms 69404 KB Output is correct
20 Correct 470 ms 66952 KB Output is correct
21 Correct 450 ms 69440 KB Output is correct
22 Correct 447 ms 66980 KB Output is correct
23 Correct 439 ms 66932 KB Output is correct
24 Correct 460 ms 66956 KB Output is correct
25 Correct 458 ms 67004 KB Output is correct
26 Correct 504 ms 69524 KB Output is correct
27 Correct 472 ms 69452 KB Output is correct
28 Correct 462 ms 66952 KB Output is correct
29 Correct 457 ms 67008 KB Output is correct
30 Correct 464 ms 66960 KB Output is correct