oj.uz

Submission #1121301

# Submission time Handle Problem Language Result Execution time Memory
1121301 2024-11-28T17:53:49 Z Irate Wall (IOI14_wall) C++17
100 / 100
 796 ms 161992 KB 
#include<bits/stdc++.h>
using namespace std;
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
struct Node{
    int l = -1, r = -1;
};
Node intersect(Node &cur, Node &upd){
    if(cur.l < 0){
        return upd;
    }
    if(upd.l > cur.r){
        return {upd.l, upd.l};
    }
    else if(cur.l > upd.r){
        return {upd.r, upd.r};
    }
    else if(cur.l <= upd.l && upd.l <= cur.r && cur.r <= upd.r){
        return {upd.l, cur.r};
    }
    else if(upd.l <= cur.l && cur.l <= upd.r && upd.r <= cur.r){
        return {cur.l, upd.r};
    }
    else if(cur.l <= upd.l && upd.r <= cur.r){
        return upd;
    }
    return cur;
}
struct SegmentTree{
    vector<Node>sTree, lazy;
    void init(int n){
        sTree.resize(4 * n);
        lazy.resize(4 * n);
    }
    void Propagate(int node, int l, int r){
        if(lazy[node].l < 0)return;
        if(l != r){
            lazy[node * 2] = intersect(lazy[node * 2], lazy[node]);
            lazy[node * 2 + 1] = intersect(lazy[node * 2 + 1], lazy[node]);
        }
        else{
            sTree[node] = intersect(sTree[node], lazy[node]);
        }
        lazy[node] = {-1, -1};
    }
    void Build(int node, int l, int r){
        if(l == r){
            sTree[node] = {0, 0};
        }
        else{
            int mid = (l + r) >> 1;
            Build(node * 2, l, mid);
            Build(node * 2 + 1, mid + 1, r);
        }
    }
    void R_Update(int node, int l, int r, int ql, int qr, int type, int x){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            if(type == 2){
                lazy[node] = {0, x};
            }
            else{
                lazy[node] = {x, 100000};
            }
            Propagate(node, l, r);
            return;
        }
        if(ql > r || l > qr){
            return;
        }
        int mid = (l + r) >> 1;
        R_Update(node * 2, l, mid, ql, qr, type, x);
        R_Update(node * 2 + 1, mid + 1, r, ql, qr, type, x);
    }
    int Get(int node, int l, int r, int pos){
        Propagate(node, l, r);
        if(l == r){
            return sTree[node].l;
        }
        else{
            int mid = (l + r) >> 1;
            if(pos <= mid){
                return Get(node * 2, l, mid, pos);
            }
            else{
                return Get(node * 2 + 1, mid + 1, r, pos);
            }
        }
    }
} tree;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    tree.init(n);
    tree.Build(1, 1, n);
    for(int i = 0;i < k;++i){
        tree.R_Update(1, 1, n, left[i] + 1, right[i] + 1, op[i], height[i]);
    }
    for(int i = 1;i <= n;++i){
        finalHeight[i - 1] = tree.Get(1, 1, n, i);
    }
}
// int main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     int n, q;
//     cin >> n >> q;
//     int op[q], left[q], right[q], height[q], finalHeight[n];
//     for(int i = 0;i < q;++i){
//         cin >> op[i] >> left[i] >> right[i] >> height[i];
//     }
//     buildWall(n, q, op, left, right, height, finalHeight);
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 10 ms 1108 KB Output is correct
5 Correct 8 ms 1108 KB Output is correct
6 Correct 5 ms 1120 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 128 ms 14056 KB Output is correct
3 Correct 206 ms 8524 KB Output is correct
4 Correct 617 ms 24696 KB Output is correct
5 Correct 250 ms 25800 KB Output is correct
6 Correct 240 ms 24140 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 1108 KB Output is correct
5 Correct 4 ms 1272 KB Output is correct
6 Correct 6 ms 1108 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 88 ms 13900 KB Output is correct
9 Correct 226 ms 8596 KB Output is correct
10 Correct 618 ms 24688 KB Output is correct
11 Correct 231 ms 25664 KB Output is correct
12 Correct 203 ms 24168 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 117 ms 14004 KB Output is correct
15 Correct 31 ms 2576 KB Output is correct
16 Correct 658 ms 24848 KB Output is correct
17 Correct 238 ms 24396 KB Output is correct
18 Correct 256 ms 24392 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 7 ms 1212 KB Output is correct
5 Correct 5 ms 1364 KB Output is correct
6 Correct 5 ms 1156 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 115 ms 13856 KB Output is correct
9 Correct 227 ms 8556 KB Output is correct
10 Correct 655 ms 24632 KB Output is correct
11 Correct 232 ms 25668 KB Output is correct
12 Correct 201 ms 24140 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 111 ms 13892 KB Output is correct
15 Correct 39 ms 2576 KB Output is correct
16 Correct 673 ms 24804 KB Output is correct
17 Correct 239 ms 24396 KB Output is correct
18 Correct 202 ms 24364 KB Output is correct
19 Correct 746 ms 161608 KB Output is correct
20 Correct 688 ms 159196 KB Output is correct
21 Correct 717 ms 161852 KB Output is correct
22 Correct 742 ms 159592 KB Output is correct
23 Correct 717 ms 159448 KB Output is correct
24 Correct 731 ms 159564 KB Output is correct
25 Correct 678 ms 159532 KB Output is correct
26 Correct 720 ms 161540 KB Output is correct
27 Correct 686 ms 161992 KB Output is correct
28 Correct 707 ms 159564 KB Output is correct
29 Correct 784 ms 159468 KB Output is correct
30 Correct 796 ms 159596 KB Output is correct