oj.uz

Submission #321609

# Submission time Handle Problem Language Result Execution time Memory
321609 2020-11-12T21:27:50 Z nikatamliani Wall (IOI14_wall) C++14
100 / 100
 877 ms 99692 KB 
#include <bits/stdc++.h>
using namespace std;
const int oo = 1e9 + 6; 
struct node {
    int maxi, mini;
    node() {
        mini = oo;
        maxi = 0; 
    }
};
vector<node> tree;
void apply(int p, int L, int R) {
    node& me = tree[p];
    me.mini = max(min(me.mini, R), L);
    me.maxi = max(min(me.maxi, R), L);
}
void push(int l, int r, int p) {
    node& me = tree[p];
    if(l < r) {
        apply(p << 1, me.maxi, me.mini);
        apply(p << 1 | 1, me.maxi, me.mini);
    }
    me.mini = oo;
    me.maxi = 0;
}
void update(int l, int r, int L, int R, int val_L, int val_R, int p) {
    if(l > R || L > r) return;
    if(L <= l && R >= r) {
        apply(p, val_L, val_R);
    } else {
        push(l, r, p); 
        int m = l + r >> 1;
        update(l, m, L, R, val_L, val_R, p << 1);
        update(m + 1, r, L, R, val_L, val_R, p << 1 | 1);
    }
}
void traverse(int l, int r, int p, int finalHeight[]) {
    if(l == r) {
        finalHeight[l - 1] = tree[p].maxi;
    } else {
        push(l, r, p);
        int m = l + r >> 1;
        traverse(l, m, p << 1, finalHeight);
        traverse(m + 1, r, p << 1 | 1, finalHeight);
    } 
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    tree.resize(4 * n + 1);
    for(int i = 0; i < k; ++i) {
        if(op[i] == 1) {
            update(1, n, left[i] + 1, right[i] + 1, height[i], oo, 1);
        } else {
            update(1, n, left[i] + 1, right[i] + 1, -oo, height[i], 1);
        }
    }
    traverse(1, n, 1, finalHeight);
}
// int main() {
//     int n, k;
//     cin >> n >> k;
//     int op[k], left[k], right[k], height[k], finalHeight[k];
//     memset(finalHeight, -1, sizeof finalHeight);
//     for(int i = 0; i < k; ++i) {
//         cin >> op[i] >> left[i] >> right[i] >> height[i];
//     }
//     buildWall(n, k, op, left, right, height, finalHeight);
//     for(int i = 0; i < n; ++i) {
//         cout << finalHeight[i] << ' '; 
//     }
// }

Compilation message

wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int m = l + r >> 1;
      |                 ~~^~~
wall.cpp: In function 'void traverse(int, int, int, int*)':
wall.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 158 ms 14060 KB Output is correct
3 Correct 190 ms 8044 KB Output is correct
4 Correct 531 ms 21612 KB Output is correct
5 Correct 356 ms 22636 KB Output is correct
6 Correct 361 ms 20972 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 156 ms 13932 KB Output is correct
9 Correct 193 ms 8172 KB Output is correct
10 Correct 538 ms 21604 KB Output is correct
11 Correct 360 ms 22508 KB Output is correct
12 Correct 344 ms 21012 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 158 ms 13932 KB Output is correct
15 Correct 31 ms 2028 KB Output is correct
16 Correct 547 ms 21892 KB Output is correct
17 Correct 352 ms 21204 KB Output is correct
18 Correct 345 ms 21248 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 159 ms 13932 KB Output is correct
9 Correct 194 ms 8044 KB Output is correct
10 Correct 546 ms 21612 KB Output is correct
11 Correct 361 ms 22508 KB Output is correct
12 Correct 343 ms 21228 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 161 ms 14140 KB Output is correct
15 Correct 32 ms 2028 KB Output is correct
16 Correct 546 ms 21868 KB Output is correct
17 Correct 348 ms 21504 KB Output is correct
18 Correct 354 ms 21228 KB Output is correct
19 Correct 864 ms 99692 KB Output is correct
20 Correct 863 ms 96988 KB Output is correct
21 Correct 869 ms 99308 KB Output is correct
22 Correct 851 ms 96876 KB Output is correct
23 Correct 850 ms 96940 KB Output is correct
24 Correct 860 ms 96876 KB Output is correct
25 Correct 853 ms 96876 KB Output is correct
26 Correct 858 ms 99352 KB Output is correct
27 Correct 861 ms 99564 KB Output is correct
28 Correct 877 ms 96876 KB Output is correct
29 Correct 852 ms 96920 KB Output is correct
30 Correct 849 ms 96876 KB Output is correct