oj.uz

Submission #138892

# Submission time Handle Problem Language Result Execution time Memory
138892 2019-07-30T19:58:03 Z jovan_b Wall (IOI14_wall) C++17
100 / 100
 852 ms 70700 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;

pair <int, int> seg[8000005];

void init(int node, int l, int r){
    seg[node].first = INF;
    if(l == r) return;
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
}

void update_children(int node, int l, int r){
    if(l == r) return;
    seg[node*2].first = min(seg[node*2].first, seg[node].first);
    seg[node*2].first = max(seg[node*2].first, seg[node].second);
    seg[node*2].second = max(seg[node*2].second, seg[node].second);
    seg[node*2].second = min(seg[node*2].second, seg[node].first);
    seg[node*2+1].first = min(seg[node*2+1].first, seg[node].first);
    seg[node*2+1].first = max(seg[node*2+1].first, seg[node].second);
    seg[node*2+1].second = max(seg[node*2+1].second, seg[node].second);
    seg[node*2+1].second = min(seg[node*2+1].second, seg[node].first);
    seg[node].first = INF;
    seg[node].second = 0;
}

void upd(int node, int l, int r, int tl, int tr, pair <int, int> val){
    update_children(node, l, r);
    if(l > tr || tl > r) return;
    if(tl <= l && r <= tr){
        seg[node].first = min(seg[node].first, val.first);
        seg[node].first = max(seg[node].first, val.second);
        seg[node].second = max(seg[node].second, val.second);
        seg[node].second = min(seg[node].second, val.first);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, val);
    upd(node*2+1, mid+1, r, tl, tr, val);
}

int konacno[2000005];

void traverse(int node, int l, int r){
    update_children(node, l, r);
    if(l == r){
        konacno[l-1] = min(seg[node].first, seg[node].second);
        return;
    }
    int mid = (l+r)/2;
    traverse(node*2, l, mid);
    traverse(node*2+1, mid+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    init(1, 1, n);
    for(int i=0; i<k; i++){
        if(op[i] == 2){
            upd(1, 1, n, left[i]+1, right[i]+1, {height[i], 0});
        }
        else{
            upd(1, 1, n, left[i]+1, right[i]+1, {INF, height[i]});
        }
    }
    traverse(1, 1, n);
    for(int i=0; i<n; i++){
        finalHeight[i] = konacno[i];
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 173 ms 11736 KB Output is correct
3 Correct 222 ms 7928 KB Output is correct
4 Correct 638 ms 14812 KB Output is correct
5 Correct 379 ms 15352 KB Output is correct
6 Correct 364 ms 15352 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 8 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 173 ms 11844 KB Output is correct
9 Correct 212 ms 7928 KB Output is correct
10 Correct 643 ms 14928 KB Output is correct
11 Correct 371 ms 15356 KB Output is correct
12 Correct 360 ms 15352 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 177 ms 11800 KB Output is correct
15 Correct 36 ms 2040 KB Output is correct
16 Correct 626 ms 15132 KB Output is correct
17 Correct 377 ms 15096 KB Output is correct
18 Correct 369 ms 15068 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 9 ms 888 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 8 ms 920 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 175 ms 11896 KB Output is correct
9 Correct 216 ms 7928 KB Output is correct
10 Correct 607 ms 14800 KB Output is correct
11 Correct 380 ms 15376 KB Output is correct
12 Correct 369 ms 15416 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 176 ms 11868 KB Output is correct
15 Correct 36 ms 2168 KB Output is correct
16 Correct 603 ms 15160 KB Output is correct
17 Correct 366 ms 15160 KB Output is correct
18 Correct 384 ms 15228 KB Output is correct
19 Correct 848 ms 70700 KB Output is correct
20 Correct 846 ms 68072 KB Output is correct
21 Correct 852 ms 70572 KB Output is correct
22 Correct 838 ms 68080 KB Output is correct
23 Correct 823 ms 67960 KB Output is correct
24 Correct 849 ms 68104 KB Output is correct
25 Correct 842 ms 68088 KB Output is correct
26 Correct 847 ms 70520 KB Output is correct
27 Correct 833 ms 70648 KB Output is correct
28 Correct 827 ms 68088 KB Output is correct
29 Correct 827 ms 68088 KB Output is correct
30 Correct 833 ms 68060 KB Output is correct