oj.uz

Submission #1087427

# Submission time Handle Problem Language Result Execution time Memory
1087427 2024-09-12T16:52:15 Z dwuy Wall (IOI14_wall) C++14
100 / 100
 733 ms 89284 KB 
/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 2e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

struct SMT{
    int n;
    vector<pii> tree;

    SMT(int n = 0) : n(n), tree(n<<2|3, {0, OO}) {}

    pii combine(pii a, pii b){ /// a -> b;
        a.fi = max(a.fi, b.fi);
        a.se = max(a.se, a.fi);
        a.se = min(a.se, b.se);
        a.fi = min(a.fi, a.se);
        return a;
    }

    void down(int id){
        int ID = id<<1;
        tree[ID] = combine(tree[ID], tree[id]);
        tree[ID|1] = combine(tree[ID|1], tree[id]);
        tree[id] = {0, OO};
    }

    void update(int l, int r, int id, const int &u, const int v, const pii &rv){
        if(l > v || r < u) return;
        if(l >= u && r <= v){
            tree[id] = combine(tree[id], rv);
            return;
        }
        down(id);
        int mid = (l + r)>>1;
        update(l, mid, id<<1, u, v, rv);
        update(mid + 1, r, id<<1|1, u, v, rv);
    }

    void update(int u, int v, pii rv){
        update(1, n, 1, u, v, rv);
    }

    int get(int pos){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            down(id);
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1|1;
        }
        return tree[id].fi;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int res[]){
    SMT smt(n);
    for(int i=0; i<k; i++){
        if(op[i] == 1) smt.update(left[i] + 1, right[i] + 1, {height[i], INF});
        else smt.update(left[i] + 1, right[i] + 1, {-INF, height[i]});
    }
    for(int i=1; i<=n; i++) res[i-1] = smt.get(i);
}

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 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 860 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 0 ms 348 KB Output is correct
2 Correct 101 ms 13916 KB Output is correct
3 Correct 103 ms 8016 KB Output is correct
4 Correct 301 ms 21300 KB Output is correct
5 Correct 211 ms 21844 KB Output is correct
6 Correct 190 ms 20556 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 568 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 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 94 ms 13916 KB Output is correct
9 Correct 109 ms 8016 KB Output is correct
10 Correct 311 ms 21328 KB Output is correct
11 Correct 210 ms 21844 KB Output is correct
12 Correct 188 ms 20200 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 91 ms 13884 KB Output is correct
15 Correct 18 ms 1880 KB Output is correct
16 Correct 320 ms 21340 KB Output is correct
17 Correct 199 ms 20756 KB Output is correct
18 Correct 213 ms 20644 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 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 89 ms 13820 KB Output is correct
9 Correct 116 ms 8020 KB Output is correct
10 Correct 302 ms 21332 KB Output is correct
11 Correct 199 ms 21840 KB Output is correct
12 Correct 193 ms 20192 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 90 ms 13940 KB Output is correct
15 Correct 18 ms 1980 KB Output is correct
16 Correct 301 ms 21344 KB Output is correct
17 Correct 206 ms 20560 KB Output is correct
18 Correct 198 ms 20688 KB Output is correct
19 Correct 710 ms 89168 KB Output is correct
20 Correct 710 ms 89284 KB Output is correct
21 Correct 698 ms 88936 KB Output is correct
22 Correct 717 ms 88916 KB Output is correct
23 Correct 704 ms 89004 KB Output is correct
24 Correct 733 ms 88912 KB Output is correct
25 Correct 728 ms 89008 KB Output is correct
26 Correct 700 ms 89016 KB Output is correct
27 Correct 723 ms 89004 KB Output is correct
28 Correct 716 ms 89200 KB Output is correct
29 Correct 710 ms 88912 KB Output is correct
30 Correct 710 ms 89000 KB Output is correct