oj.uz

Submission #1098832

# Submission time Handle Problem Language Result Execution time Memory
1098832 2024-10-10T07:07:35 Z Zero_OP Wall (IOI14_wall) C++14
100 / 100
 799 ms 89288 KB 
#include "bits/stdc++.h"
#ifndef LOCAL
#include "wall.h"
#endif

using namespace std;

struct item{
    int l, r;
    item(int l = 0, int r = INT_MAX) : l(l), r(r) {}
};

struct SegmentTree{
    vector<item> st;
    SegmentTree(int n) : st(n << 2) {}

    void apply(int id, const item& val){
        st[id].l = max(st[id].l, val.l);
        st[id].l = min(st[id].l, val.r);
        st[id].r = max(st[id].r, val.l);
        st[id].r = min(st[id].r, val.r);
    }

    void lazyDown(int id){
        apply(id << 1, st[id]);
        apply(id << 1 | 1, st[id]);
        st[id] = item();
    }

    void update(int id, int l, int r, int u, int v, const item& val){
        if(u <= l && r <= v){
            apply(id, val);
        } else{
            int mid = l + r >> 1;
            lazyDown(id);

            if(u <= mid) update(id << 1, l, mid, u, v, val);
            if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
        }
    }

    item query(int id, int l, int r, int k){
        if(l == r) return st[id];
        int mid = l + r >> 1;
        lazyDown(id);

        if(k <= mid) return query(id << 1, l, mid, k);
        else return query(id << 1 | 1, mid + 1, r, k);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegmentTree T(n);
    for(int i = 0; i < k; ++i){
        if(op[i] == 1){
            T.update(1, 0, n - 1, left[i], right[i], {height[i], INT_MAX});
        } else{
            T.update(1, 0, n - 1, left[i], right[i], {0, height[i]});
        }
    }

    for(int i = 0; i < n; ++i){
        finalHeight[i] = T.query(1, 0, n - 1, i).l;
    }
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n = 10, k = 6;
    int op[] = {1, 2, 2, 1, 1, 2}, left[] = {1, 4, 3, 0, 2, 6}, right[] = {8, 9, 6, 5, 2, 7}, height[] = {4, 1, 5, 3, 5, 0};
    int finalHeight[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    buildWall(n, k, op, left, right, height, finalHeight);
    for(int i = 0; i < n; ++i){
        cout << finalHeight[i] << ' ';
    }
    cout << '\n';

    return 0;
}
#endif

Compilation message

wall.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, const item&)':
wall.cpp:34:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |             int mid = l + r >> 1;
      |                       ~~^~~
wall.cpp: In member function 'item SegmentTree::query(int, int, int, int)':
wall.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 94 ms 14028 KB Output is correct
3 Correct 116 ms 8032 KB Output is correct
4 Correct 355 ms 21332 KB Output is correct
5 Correct 222 ms 21844 KB Output is correct
6 Correct 196 ms 20308 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 892 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 90 ms 13984 KB Output is correct
9 Correct 114 ms 8020 KB Output is correct
10 Correct 337 ms 21332 KB Output is correct
11 Correct 219 ms 21844 KB Output is correct
12 Correct 200 ms 20308 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 86 ms 13932 KB Output is correct
15 Correct 20 ms 1884 KB Output is correct
16 Correct 344 ms 21268 KB Output is correct
17 Correct 240 ms 20712 KB Output is correct
18 Correct 208 ms 20584 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 85 ms 13968 KB Output is correct
9 Correct 115 ms 8020 KB Output is correct
10 Correct 339 ms 21332 KB Output is correct
11 Correct 200 ms 21844 KB Output is correct
12 Correct 187 ms 20304 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 81 ms 14000 KB Output is correct
15 Correct 19 ms 2136 KB Output is correct
16 Correct 321 ms 21280 KB Output is correct
17 Correct 213 ms 20740 KB Output is correct
18 Correct 210 ms 20624 KB Output is correct
19 Correct 779 ms 89172 KB Output is correct
20 Correct 763 ms 88916 KB Output is correct
21 Correct 782 ms 88912 KB Output is correct
22 Correct 766 ms 89016 KB Output is correct
23 Correct 760 ms 88916 KB Output is correct
24 Correct 711 ms 89288 KB Output is correct
25 Correct 767 ms 89168 KB Output is correct
26 Correct 770 ms 88920 KB Output is correct
27 Correct 799 ms 88916 KB Output is correct
28 Correct 747 ms 88912 KB Output is correct
29 Correct 754 ms 88936 KB Output is correct
30 Correct 709 ms 89172 KB Output is correct