oj.uz

Submission #828011

# Submission time Handle Problem Language Result Execution time Memory
828011 2023-08-17T01:22:47 Z jlallas384 Wall (IOI14_wall) C++17
100 / 100
 888 ms 224608 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

struct Seg{
    int l,r;
    Seg(): l(0), r(100000){}
    Seg(int l, int r): l(l), r(r){}
    void apply(Seg oth){
        if(r < oth.l){
            l = r = oth.l;
        }else if(oth.r < l){
            l = r = oth.r;
        }else{
            l = max(l, oth.l);
            r = min(r, oth.r);
        }
    }
};

struct Tree{
    Tree *lc, *rc;
    Seg val;
    int l, r;
    Tree(int l, int r): l(l), r(r){
        if(l == r) val = Seg(0, 0);
        else{
            int m = (l + r) / 2;
            lc = new Tree(l, m), rc = new Tree(m + 1, r);
        }
    }
    void push(){
        if(l != r){
            lc->val.apply(val);
            rc->val.apply(val);
        }
        val = Seg();
    }
    void upd(int i, int j, Seg x){
        if(r < i || j < l) return;
        if(i <= l && r <= j){
            val.apply(x);
        }else{
            push();
            lc->upd(i, j, x), rc->upd(i, j, x);
        }
    }
    int qry(int i){
        if(l == r) return val.l;
        else{
            push();
            if(i <= lc->r) return lc->qry(i);
            else return rc->qry(i);
        }
    }
};


void buildWall(int n, int k, int op[], int l[], int r[], int height[], int finalHeight[]){
    Tree *st = new Tree(0, n - 1);
    for(int i = 0; i < k; i++){
        if(op[i] == 1){
            st->upd(l[i], r[i], Seg(height[i], 100000));
        }else{
            st->upd(l[i], r[i], Seg(0, height[i]));
        }
    }
    for(int i = 0; i < n; i++){
        finalHeight[i] = st->qry(i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 1492 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 5 ms 1396 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 103 ms 13912 KB Output is correct
3 Correct 152 ms 9072 KB Output is correct
4 Correct 377 ms 27640 KB Output is correct
5 Correct 214 ms 28748 KB Output is correct
6 Correct 205 ms 27144 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 1492 KB Output is correct
5 Correct 5 ms 1388 KB Output is correct
6 Correct 5 ms 1468 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 105 ms 13928 KB Output is correct
9 Correct 121 ms 9088 KB Output is correct
10 Correct 361 ms 27672 KB Output is correct
11 Correct 212 ms 28748 KB Output is correct
12 Correct 202 ms 27180 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 110 ms 13924 KB Output is correct
15 Correct 29 ms 3072 KB Output is correct
16 Correct 457 ms 27896 KB Output is correct
17 Correct 215 ms 27296 KB Output is correct
18 Correct 209 ms 27364 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 360 KB Output is correct
4 Correct 6 ms 1460 KB Output is correct
5 Correct 5 ms 1392 KB Output is correct
6 Correct 6 ms 1492 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 104 ms 13884 KB Output is correct
9 Correct 119 ms 9096 KB Output is correct
10 Correct 379 ms 27640 KB Output is correct
11 Correct 211 ms 28748 KB Output is correct
12 Correct 202 ms 27132 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 111 ms 13828 KB Output is correct
15 Correct 26 ms 3092 KB Output is correct
16 Correct 462 ms 27896 KB Output is correct
17 Correct 213 ms 27372 KB Output is correct
18 Correct 209 ms 27372 KB Output is correct
19 Correct 871 ms 224476 KB Output is correct
20 Correct 873 ms 222020 KB Output is correct
21 Correct 888 ms 224516 KB Output is correct
22 Correct 858 ms 222104 KB Output is correct
23 Correct 854 ms 221960 KB Output is correct
24 Correct 884 ms 222008 KB Output is correct
25 Correct 857 ms 222012 KB Output is correct
26 Correct 855 ms 224500 KB Output is correct
27 Correct 879 ms 224608 KB Output is correct
28 Correct 855 ms 221924 KB Output is correct
29 Correct 855 ms 221944 KB Output is correct
30 Correct 859 ms 222052 KB Output is correct