oj.uz

Submission #466682

# Submission time Handle Problem Language Result Execution time Memory
466682 2021-08-20T05:25:10 Z jli12345 Wall (IOI14_wall) C++14
100 / 100
 1614 ms 69688 KB 
#include <wall.h>
#include <bits/stdc++.h>
using namespace std;

pair<int, int> st[8000100];

pair<int, int> combine(pair<int, int> orig, pair<int, int> upd){
    if (upd.second > orig.first){
        return {upd.second, upd.second};
    } else if (upd.first < orig.second){
        return {upd.first, upd.first};
    } else {
        return {min(orig.first, upd.first), max(orig.second, upd.second)};
    }
}

void pushdown(int node){
    st[node*2] = combine(st[node*2], st[node]);
    st[node*2+1] = combine(st[node*2+1], st[node]);
}

void U(int node, int l, int r, int tl, int tr, pair<int, int> upd){
    if (l >tr || r < tl)
        return;
    if (l >= tl && r <= tr){
        st[node] = combine(st[node], upd);
        //cout << l << " " << r << " " << st[node].first << " " << st[node].second << "\n";
        return;
    }
    pushdown(node);
    int mid = (l+r)/2;
    U(node*2, l, mid, tl, tr, upd);
    U(node*2+1, mid+1, r, tl, tr, upd);
    st[node].first = max(st[node*2].first, st[node*2+1].first);
    st[node].second = min(st[node*2].second, st[node*2+1].second);
}

int Q(int node, int l, int r, int ind){
    if (l > ind || r < ind){
        return 0;
    }
    if (l == r){
        return st[node].first;
    }
    pushdown(node);
    int mid = (l+r)/2;
    st[node].first = max(st[node*2].first, st[node*2+1].first);
    st[node].second = min(st[node*2].second, st[node*2+1].second);
    return max(Q(node*2, l, mid, ind), Q(node*2+1, mid+1, r, ind));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; i++){
        if (op[i] == 1){
            U(1, 0, n-1, left[i], right[i], {0x3f3f3f3f, height[i]});
        } else {
            U(1, 0, n-1, left[i], right[i], {height[i], 0});
        }
    }
    for (int i = 0; i < n; i++){
        finalHeight[i] = Q(1, 0, n-1, i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 788 KB Output is correct
5 Correct 8 ms 760 KB Output is correct
6 Correct 8 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 163 ms 13952 KB Output is correct
3 Correct 201 ms 7908 KB Output is correct
4 Correct 578 ms 20340 KB Output is correct
5 Correct 405 ms 21372 KB Output is correct
6 Correct 380 ms 19872 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 716 KB Output is correct
5 Correct 8 ms 764 KB Output is correct
6 Correct 9 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 171 ms 13956 KB Output is correct
9 Correct 196 ms 8004 KB Output is correct
10 Correct 582 ms 20328 KB Output is correct
11 Correct 381 ms 21444 KB Output is correct
12 Correct 377 ms 19780 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 166 ms 13892 KB Output is correct
15 Correct 39 ms 1952 KB Output is correct
16 Correct 635 ms 20572 KB Output is correct
17 Correct 398 ms 19972 KB Output is correct
18 Correct 389 ms 20088 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 760 KB Output is correct
5 Correct 8 ms 764 KB Output is correct
6 Correct 8 ms 808 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 163 ms 13932 KB Output is correct
9 Correct 195 ms 7872 KB Output is correct
10 Correct 582 ms 20472 KB Output is correct
11 Correct 392 ms 21360 KB Output is correct
12 Correct 383 ms 19764 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 172 ms 13896 KB Output is correct
15 Correct 38 ms 2000 KB Output is correct
16 Correct 653 ms 20568 KB Output is correct
17 Correct 385 ms 19964 KB Output is correct
18 Correct 390 ms 20036 KB Output is correct
19 Correct 1576 ms 69400 KB Output is correct
20 Correct 1565 ms 67000 KB Output is correct
21 Correct 1587 ms 69572 KB Output is correct
22 Correct 1568 ms 66952 KB Output is correct
23 Correct 1578 ms 67132 KB Output is correct
24 Correct 1570 ms 67004 KB Output is correct
25 Correct 1571 ms 67064 KB Output is correct
26 Correct 1600 ms 69408 KB Output is correct
27 Correct 1588 ms 69688 KB Output is correct
28 Correct 1602 ms 66884 KB Output is correct
29 Correct 1597 ms 66892 KB Output is correct
30 Correct 1614 ms 67064 KB Output is correct