oj.uz

Submission #1094502

# Submission time Handle Problem Language Result Execution time Memory
1094502 2024-09-29T17:20:26 Z anhthi Wall (IOI14_wall) C++14
100 / 100
 413 ms 89168 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }

template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 998244353;

const int mxn = 2e5 + 5, LOG = 18;

void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

struct Seg {

    int n;
    vector<pair<int, int>> st;

    Seg(int n) : n(n) {
        st.resize(n << 2);
    }

    void setNode(int i, pair<int, int> val) {
        if (st[i].first > val.second) st[i] = mp(val.second, val.second);
        else if (st[i].second < val.first) st[i] = mp(val.first, val.first);
        else {
            st[i] = mp(max(st[i].first, val.first), min(st[i].second, val.second));
        }
    }

    void down(int i) {
        if (st[i] == mp(-inf, inf))
            return;
        setNode(2 * i, st[i]);
        setNode(2 * i + 1, st[i]);
        st[i] = mp(-inf, inf);
    }

    void upd(int i, int l, int r, int u, int v, pair<int, int> val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) return setNode(i, val);
        down(i);
        int m = (l + r) >> 1;
        upd(2 * i, l, m, u, v, val);
        upd(2 * i + 1, m + 1, r, u, v, val);
    }

    void upd(int u, int v, pair<int, int> val) {
        return upd(1, 0, n - 1, u, v, val);
    }

    void dfs(int i, int l, int r, int ans[]) {
        if (l == r) {
            ans[l] = st[i].first;
            return;
        }
        down(i);
        int m = (l + r) >> 1;
        dfs(2 * i, l, m, ans);
        dfs(2 * i + 1, m + 1, r, ans);
    }
    void dfs(int ans[]) { return dfs(1, 0, n - 1, ans); }
};

void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){
    Seg s(n);
    forn(i, 0, k - 1) {
        int l = L[i];
        int r = R[i];
        int h = H[i];
        if (op[i] == 1)
            s.upd(l, r, mp(h, inf));
        else s.upd(l, r, mp(-inf, h));
    }
    s.dfs(ans);
    return;
}

//int main(void) {
//
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    #define TASK "task"
//    if (fopen(TASK".inp", "r")) {
//        freopen(TASK".inp", "r", stdin);
//        freopen(TASK".out", "w", stdout);
//    }
//
//    int n = 10, k = 6;
//    int op[] = {1, 2, 2, 1, 1, 2};
//    int L[] = {1, 4, 3, 0, 2, 6};
//    int R[] = {8, 9, 6, 5, 2, 7};
//    int H[] = {4, 1, 5, 3, 5, 0};
//
//    int ans[n];
//    memset(ans, 0, sizeof ans);
//    buildWall(n, k, op, L, R, H, ans);
//
//    forn(i, 0, n - 1) cout << ans[i] << ' ';
//
//    return 0;
//}

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 3 ms 932 KB Output is correct
6 Correct 3 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 82 ms 14092 KB Output is correct
3 Correct 103 ms 8016 KB Output is correct
4 Correct 291 ms 21236 KB Output is correct
5 Correct 153 ms 21840 KB Output is correct
6 Correct 146 ms 20264 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 13860 KB Output is correct
9 Correct 103 ms 8020 KB Output is correct
10 Correct 300 ms 21384 KB Output is correct
11 Correct 163 ms 21896 KB Output is correct
12 Correct 154 ms 20268 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 90 ms 14024 KB Output is correct
15 Correct 22 ms 1884 KB Output is correct
16 Correct 413 ms 21452 KB Output is correct
17 Correct 155 ms 20820 KB Output is correct
18 Correct 162 ms 20816 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 3 ms 964 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 86 ms 13908 KB Output is correct
9 Correct 105 ms 8100 KB Output is correct
10 Correct 288 ms 21336 KB Output is correct
11 Correct 159 ms 21776 KB Output is correct
12 Correct 146 ms 20304 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 89 ms 13912 KB Output is correct
15 Correct 21 ms 1880 KB Output is correct
16 Correct 387 ms 21420 KB Output is correct
17 Correct 162 ms 20940 KB Output is correct
18 Correct 158 ms 20620 KB Output is correct
19 Correct 375 ms 88916 KB Output is correct
20 Correct 365 ms 89028 KB Output is correct
21 Correct 362 ms 88916 KB Output is correct
22 Correct 365 ms 88916 KB Output is correct
23 Correct 361 ms 89120 KB Output is correct
24 Correct 362 ms 89164 KB Output is correct
25 Correct 353 ms 89164 KB Output is correct
26 Correct 364 ms 89140 KB Output is correct
27 Correct 372 ms 89168 KB Output is correct
28 Correct 371 ms 89168 KB Output is correct
29 Correct 358 ms 89168 KB Output is correct
30 Correct 360 ms 89116 KB Output is correct