oj.uz

Submission #622815

# Submission time Handle Problem Language Result Execution time Memory
622815 2022-08-04T15:22:17 Z yuto1115 Wall (IOI14_wall) C++17
100 / 100
 546 ms 75848 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

using S = P;
const S e = {0, inf};

constexpr S op(const S &l, const S &r) {
    if (l.second <= r.first) return {r.first, r.first};
    if (r.second <= l.first) return {r.second, r.second};
    return {max(l.first, r.first), min(l.second, r.second)};
}

class dual_segtree {
    int n, log;
    vector<S> d;
    
    void all_apply(int p, const S &x) {
        d[p] = op(d[p], x);
    }
    
    void push(int p) {
        all_apply(2 * p, d[p]);
        all_apply(2 * p + 1, d[p]);
        d[p] = e;
    }

public:
    dual_segtree(int _n) {
        log = 1;
        while (1 << log < _n) ++log;
        n = 1 << log;
        d.assign(2 * n, e);
    }
    
    void apply(int l, int r, const S &x) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        rrep2(i, log + 1, 1) {
            if (l >> i << i != l) push(l >> i);
            if (r >> i << i != r) push(r >> i);
        }
        while (l < r) {
            if (l & 1) all_apply(l++, x);
            if (r & 1) all_apply(--r, x);
            l >>= 1, r >>= 1;
        }
    }
    
    vector<S> all_get() {
        rep2(i, 1, n) push(i);
        return vector<S>(d.begin() + n, d.end());
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    dual_segtree st(n);
    rep(i, k) {
        ++right[i];
        if (op[i] == 1) st.apply(left[i], right[i], {height[i], inf});
        else st.apply(left[i], right[i], {0, height[i]});
    }
    auto ans = st.all_get();
    rep(i, n) finalHeight[i] = ans[i].first;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 824 KB Output is correct
6 Correct 4 ms 884 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 124 ms 13896 KB Output is correct
3 Correct 112 ms 8176 KB Output is correct
4 Correct 307 ms 21224 KB Output is correct
5 Correct 235 ms 21696 KB Output is correct
6 Correct 231 ms 20172 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 880 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 123 ms 13864 KB Output is correct
9 Correct 114 ms 8068 KB Output is correct
10 Correct 313 ms 21216 KB Output is correct
11 Correct 241 ms 21772 KB Output is correct
12 Correct 235 ms 20200 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 133 ms 13948 KB Output is correct
15 Correct 24 ms 2108 KB Output is correct
16 Correct 402 ms 21192 KB Output is correct
17 Correct 246 ms 20608 KB Output is correct
18 Correct 240 ms 20648 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 126 ms 13912 KB Output is correct
9 Correct 118 ms 8168 KB Output is correct
10 Correct 308 ms 21344 KB Output is correct
11 Correct 241 ms 21768 KB Output is correct
12 Correct 232 ms 20164 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 134 ms 13856 KB Output is correct
15 Correct 27 ms 2144 KB Output is correct
16 Correct 403 ms 21224 KB Output is correct
17 Correct 255 ms 20640 KB Output is correct
18 Correct 243 ms 20604 KB Output is correct
19 Correct 527 ms 75688 KB Output is correct
20 Correct 527 ms 75848 KB Output is correct
21 Correct 525 ms 75676 KB Output is correct
22 Correct 523 ms 75592 KB Output is correct
23 Correct 514 ms 75724 KB Output is correct
24 Correct 522 ms 75544 KB Output is correct
25 Correct 546 ms 75788 KB Output is correct
26 Correct 541 ms 75664 KB Output is correct
27 Correct 529 ms 75700 KB Output is correct
28 Correct 520 ms 75572 KB Output is correct
29 Correct 518 ms 75636 KB Output is correct
30 Correct 532 ms 75592 KB Output is correct