oj.uz

Submission #795668

# Submission time Handle Problem Language Result Execution time Memory
795668 2023-07-27T12:37:53 Z chanhchuong123 Wall (IOI14_wall) C++14
100 / 100
 574 ms 77316 KB 
//#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;
const int MAX = 2000020;
int n, h[MAX], ans[MAX];
pair<int, int> st[MAX << 2];

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

void update(int id, int l, int r) {
    if (st[id].first > r) st[id] = make_pair(r, r); else
    if (st[id].second < l) st[id] = make_pair(l, l); else
    st[id] = make_pair(max(l, st[id].first), min(r, st[id].second));
}

void push(int id) {
    update(id << 1, st[id].first, st[id].second);
    update(id << 1 | 1, st[id].first, st[id].second); st[id] = make_pair(-INF, INF);
}

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

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

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

//int main(void) {
//    n = 10;
//    update(1, 1, n, 2, 9, 0, 4);
//    update(1, 1, n, 5, 10, 1, 1);
//    update(1, 1, n, 4, 7, 1, 5);
//    update(1, 1, n, 1, 6, 0, 3);
//    update(1, 1, n, 3, 3, 0, 5);
//    update(1, 1, n, 7, 8, 1, 0);
//    magic(1, 1, n);
//    for (int i = 1; i <= n; ++i) {
//        cout << ans[i] << ' ';
//    }
//}

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:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = l + r >> 1; push(id);
      |               ~~^~~
wall.cpp: In function 'void magic(int, int, int)':
wall.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = l + r >> 1; push(id);
      |               ~~^~~

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 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 5 ms 892 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 112 ms 13912 KB Output is correct
3 Correct 145 ms 8048 KB Output is correct
4 Correct 362 ms 20692 KB Output is correct
5 Correct 262 ms 21772 KB Output is correct
6 Correct 230 ms 20196 KB Output is correct

Subtask #3
29.0 / 29.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 4 ms 340 KB Output is correct
4 Correct 5 ms 836 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 111 ms 13912 KB Output is correct
9 Correct 127 ms 8056 KB Output is correct
10 Correct 397 ms 20708 KB Output is correct
11 Correct 222 ms 21780 KB Output is correct
12 Correct 227 ms 20180 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 114 ms 13920 KB Output is correct
15 Correct 26 ms 2012 KB Output is correct
16 Correct 468 ms 20968 KB Output is correct
17 Correct 231 ms 20428 KB Output is correct
18 Correct 230 ms 20460 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 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 112 ms 13916 KB Output is correct
9 Correct 125 ms 8064 KB Output is correct
10 Correct 356 ms 20748 KB Output is correct
11 Correct 227 ms 21796 KB Output is correct
12 Correct 224 ms 20172 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 117 ms 13936 KB Output is correct
15 Correct 27 ms 2012 KB Output is correct
16 Correct 461 ms 20960 KB Output is correct
17 Correct 239 ms 20420 KB Output is correct
18 Correct 241 ms 20392 KB Output is correct
19 Correct 538 ms 77280 KB Output is correct
20 Correct 541 ms 74848 KB Output is correct
21 Correct 556 ms 77316 KB Output is correct
22 Correct 527 ms 74856 KB Output is correct
23 Correct 569 ms 74776 KB Output is correct
24 Correct 530 ms 74868 KB Output is correct
25 Correct 552 ms 74788 KB Output is correct
26 Correct 574 ms 77316 KB Output is correct
27 Correct 541 ms 77280 KB Output is correct
28 Correct 531 ms 74820 KB Output is correct
29 Correct 565 ms 74940 KB Output is correct
30 Correct 541 ms 74848 KB Output is correct