oj.uz

Submission #399378

# Submission time Handle Problem Language Result Execution time Memory
399378 2021-05-05T15:57:31 Z phathnv Wall (IOI14_wall) C++11
100 / 100
 810 ms 99280 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

struct Data{
    int lo, hi;
    Data(int _lo = -1e9, int _hi = 1e9){
        lo = _lo;
        hi = _hi;
    }
    Data operator + (const Data &oth){
        if (hi < oth.lo)
            return Data(oth.lo, oth.lo);
        if (oth.hi < lo)
            return Data(oth.hi, oth.hi);
        return Data(max(lo, oth.lo), min(hi, oth.hi));
    }
};

struct SegTree{
    int n;
    vector<Data> d;
    void build(int id, int l, int r){
        if (l == r){
            d[id] = Data(0, 0);
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void init(int _n){
        n = _n;
        d.assign(n * 4 + 1, Data(-1e9, 1e9));
        build(1, 1, n);
    }
    void update(int id, int l, int r, int u, int v, Data val){
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            d[id] = d[id] + val;
            return;
        }
        d[id << 1] = d[id << 1] + d[id];
        d[id << 1 | 1] = d[id << 1 | 1] + d[id];
        d[id] = Data(-1e9, 1e9);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
    }
    void solve(int id, int l, int r, int res[]){
        if (l == r){
            assert(d[id].lo == d[id].hi);
            res[l - 1] = d[id].lo;
            return;
        }
        d[id << 1] = d[id << 1] + d[id];
        d[id << 1 | 1] = d[id << 1 | 1] + d[id];
        d[id] = Data(-1e9, 1e9);
        int mid = (l + r) >> 1;
        solve(id << 1, l, mid, res);
        solve(id << 1 | 1, mid + 1, r, res);
    }
    void update(int l, int r, Data val){
        update(1, 1, n, l, r, val);
    }
    void solve(int res[]){
        solve(1, 1, n, res);
    }
} st;

void buildWall(int n, int k, int type[], int l[], int r[], int h[], int res[]){
    st.init(n);
    for(int i = 0; i < k; i++)
        if (type[i] == 1)
            st.update(l[i] + 1, r[i] + 1, Data(h[i], 1e9));
        else
            st.update(l[i] + 1, r[i] + 1, Data(-1e9, h[i]));
    st.solve(res);
    return;
}

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 7 ms 788 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 716 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 163 ms 8068 KB Output is correct
3 Correct 176 ms 7996 KB Output is correct
4 Correct 499 ms 21480 KB Output is correct
5 Correct 325 ms 22468 KB Output is correct
6 Correct 320 ms 20996 KB Output is correct

Subtask #3
29.0 / 29.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 7 ms 720 KB Output is correct
5 Correct 6 ms 796 KB Output is correct
6 Correct 6 ms 784 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 166 ms 8028 KB Output is correct
9 Correct 177 ms 8004 KB Output is correct
10 Correct 486 ms 21404 KB Output is correct
11 Correct 324 ms 22468 KB Output is correct
12 Correct 319 ms 20868 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 177 ms 13892 KB Output is correct
15 Correct 36 ms 1988 KB Output is correct
16 Correct 611 ms 21688 KB Output is correct
17 Correct 328 ms 21056 KB Output is correct
18 Correct 326 ms 21076 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 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 6 ms 716 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 165 ms 8100 KB Output is correct
9 Correct 178 ms 8004 KB Output is correct
10 Correct 488 ms 21356 KB Output is correct
11 Correct 323 ms 22460 KB Output is correct
12 Correct 320 ms 20940 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 175 ms 13928 KB Output is correct
15 Correct 36 ms 2032 KB Output is correct
16 Correct 604 ms 21660 KB Output is correct
17 Correct 331 ms 21052 KB Output is correct
18 Correct 329 ms 21080 KB Output is correct
19 Correct 798 ms 99260 KB Output is correct
20 Correct 785 ms 96820 KB Output is correct
21 Correct 792 ms 99268 KB Output is correct
22 Correct 797 ms 96988 KB Output is correct
23 Correct 797 ms 96836 KB Output is correct
24 Correct 801 ms 96804 KB Output is correct
25 Correct 789 ms 96964 KB Output is correct
26 Correct 794 ms 99280 KB Output is correct
27 Correct 796 ms 99268 KB Output is correct
28 Correct 792 ms 96708 KB Output is correct
29 Correct 791 ms 96816 KB Output is correct
30 Correct 810 ms 96912 KB Output is correct