oj.uz

Submission #249531

# Submission time Handle Problem Language Result Execution time Memory
249531 2020-07-15T08:15:38 Z hhh07 Wall (IOI14_wall) C++14
100 / 100
 743 ms 69712 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <set>
#include <cmath>
#include <climits>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;

const int N = 1<<21;
int a[2*N + 5], b[2*N + 5];

void updateChild(int curr, int child){
    a[child] = min(a[child], a[curr]);
    a[child] = max(a[child], b[curr]);
    b[child] = max(b[child], b[curr]);
    b[child] = min(b[child], a[curr]);
}

void updateSeg(int curr, int l, int r, int beg, int end, int type, int h){
    if (l > end || r < beg)
        return;

    if (l >= beg && r <= end){
        if (!type){
            a[curr] = max(a[curr], h);
            b[curr] = max(b[curr], h);
        }
        else{
            b[curr] = min(b[curr], h);
            a[curr] = min(a[curr], h);
        }
        return;
    }
    updateChild(curr, 2*curr + 1);
    updateChild(curr, 2*curr + 2);
    a[curr] = N; b[curr] = 0;
    
    int mid = (l + r)/2;
    
    updateSeg(2*curr + 1, l, mid, beg, end, type, h);
    updateSeg(2*curr + 2, mid + 1, r, beg, end, type, h);
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    std::ios::sync_with_stdio(false);
    for (int i = 0; i < k; i++){ 
        updateSeg(0, 0, N - 1, left[i], right[i], op[i] - 1, height[i]);
    }
    for (int i = 0; i < N - 1; i++){
        updateChild(i, 2*i + 1);
        updateChild(i, 2*i + 2);
    }
    
    for (int i = N - 1; i < N + n - 1; i++)
        finalHeight[i - (N - 1)] = min(a[i], b[i]);
    
    
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 33144 KB Output is correct
2 Correct 35 ms 33272 KB Output is correct
3 Correct 35 ms 33272 KB Output is correct
4 Correct 38 ms 33400 KB Output is correct
5 Correct 38 ms 33400 KB Output is correct
6 Correct 37 ms 33400 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33144 KB Output is correct
2 Correct 341 ms 46840 KB Output is correct
3 Correct 255 ms 40312 KB Output is correct
4 Correct 599 ms 51348 KB Output is correct
5 Correct 394 ms 52312 KB Output is correct
6 Correct 379 ms 50680 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33148 KB Output is correct
2 Correct 34 ms 33280 KB Output is correct
3 Correct 33 ms 33272 KB Output is correct
4 Correct 37 ms 33400 KB Output is correct
5 Correct 38 ms 33400 KB Output is correct
6 Correct 36 ms 33400 KB Output is correct
7 Correct 32 ms 33144 KB Output is correct
8 Correct 348 ms 46840 KB Output is correct
9 Correct 240 ms 40440 KB Output is correct
10 Correct 543 ms 51192 KB Output is correct
11 Correct 394 ms 52344 KB Output is correct
12 Correct 361 ms 50680 KB Output is correct
13 Correct 31 ms 33144 KB Output is correct
14 Correct 356 ms 46844 KB Output is correct
15 Correct 63 ms 34424 KB Output is correct
16 Correct 532 ms 51584 KB Output is correct
17 Correct 373 ms 50936 KB Output is correct
18 Correct 364 ms 50936 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 33144 KB Output is correct
2 Correct 33 ms 33272 KB Output is correct
3 Correct 33 ms 33272 KB Output is correct
4 Correct 37 ms 33400 KB Output is correct
5 Correct 37 ms 33400 KB Output is correct
6 Correct 36 ms 33400 KB Output is correct
7 Correct 32 ms 33144 KB Output is correct
8 Correct 350 ms 46840 KB Output is correct
9 Correct 228 ms 40308 KB Output is correct
10 Correct 541 ms 51192 KB Output is correct
11 Correct 380 ms 52344 KB Output is correct
12 Correct 375 ms 50808 KB Output is correct
13 Correct 31 ms 33144 KB Output is correct
14 Correct 356 ms 46840 KB Output is correct
15 Correct 63 ms 34424 KB Output is correct
16 Correct 551 ms 51448 KB Output is correct
17 Correct 381 ms 50936 KB Output is correct
18 Correct 380 ms 50936 KB Output is correct
19 Correct 725 ms 69624 KB Output is correct
20 Correct 723 ms 67064 KB Output is correct
21 Correct 743 ms 69552 KB Output is correct
22 Correct 738 ms 67064 KB Output is correct
23 Correct 730 ms 67156 KB Output is correct
24 Correct 722 ms 67132 KB Output is correct
25 Correct 740 ms 67188 KB Output is correct
26 Correct 721 ms 69564 KB Output is correct
27 Correct 742 ms 69712 KB Output is correct
28 Correct 713 ms 67236 KB Output is correct
29 Correct 699 ms 67064 KB Output is correct
30 Correct 706 ms 67116 KB Output is correct