oj.uz

Submission #593899

# Submission time Handle Problem Language Result Execution time Memory
593899 2022-07-11T17:21:45 Z Do_you_copy Wall (IOI14_wall) C++17
100 / 100
 1667 ms 153864 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e6 + 1;
const int inf = 0x3f3f3f3f;
int n, k;

struct TNode{
    int mmax, mmin, lazymax, lazymin;
    TNode() : mmax(0), mmin(0), lazymax(-1), lazymin(inf){}
};

TNode st[maxN * 4];

void addmin(int id, int h){
    if (st[id].lazymin < h) return;
    st[id].lazymin = h;
    st[id].lazymax = min(st[id].lazymax, h);
    st[id].mmax = min(st[id].mmax, h);
    st[id].mmin = min(st[id].mmin, h);
}

void addmax(int id, int h){
    if (st[id].lazymax > h) return;
    st[id].lazymax = h;
    st[id].lazymin = max(st[id].lazymin, h);
    st[id].mmax = max(st[id].mmax, h);
    st[id].mmin = max(st[id].mmin, h);
}

void pull(int id){
    addmax(id * 2, st[id].lazymax);
    addmax(id * 2 + 1, st[id].lazymax);
    addmin(id * 2, st[id].lazymin);
    addmin(id * 2 + 1, st[id].lazymin);
    st[id].lazymax = -1;
    st[id].lazymin = inf;
}

void update(int id, int i, int j, int h, int t, int l = 0, int r = n - 1){
    if (r < i || l > j) return;
    if (i <= l && r <= j){
        if (t) addmin(id, h);
        else addmax(id, h);
        return;
    }
    pull(id);
    int mid = (l + r) / 2;
    update(id * 2, i, j, h, t, l, mid);
    update(id * 2 + 1, i, j, h, t, mid + 1, r);
    st[id].mmax = max(st[id * 2].mmax, st[id * 2 + 1].mmax);
    st[id].mmin = min(st[id * 2].mmin, st[id * 2 + 1].mmin);
}

int get(int id, int i, int l = 0, int r = n - 1){
    if (l == r){
        assert(st[id].mmax == st[id].mmin);
        return st[id].mmax;
    }
    //if (i == 3) cerr << l << " " << r << " " << st[id].lazymax << ":\n";
    pull(id);
    int mid = (l + r) / 2;
    if (mid >= i) return get(id * 2, i, l, mid);
    else return get(id * 2 + 1, i, mid + 1, r);
}

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N, k = K;
    for (int i = 0; i < k; ++i){
        update(1, left[i], right[i], height[i], op[i] - 1);
    }
    for (int i = 0; i < n; ++i){
        finalHeight[i] = get(1, i);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 125444 KB Output is correct
2 Correct 92 ms 125672 KB Output is correct
3 Correct 63 ms 125528 KB Output is correct
4 Correct 82 ms 125772 KB Output is correct
5 Correct 81 ms 125732 KB Output is correct
6 Correct 80 ms 125696 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125528 KB Output is correct
2 Correct 236 ms 135300 KB Output is correct
3 Correct 329 ms 130768 KB Output is correct
4 Correct 811 ms 136300 KB Output is correct
5 Correct 563 ms 136780 KB Output is correct
6 Correct 495 ms 137040 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 125432 KB Output is correct
2 Correct 68 ms 125552 KB Output is correct
3 Correct 75 ms 125576 KB Output is correct
4 Correct 74 ms 125756 KB Output is correct
5 Correct 64 ms 125700 KB Output is correct
6 Correct 66 ms 125772 KB Output is correct
7 Correct 59 ms 125436 KB Output is correct
8 Correct 229 ms 135224 KB Output is correct
9 Correct 349 ms 130780 KB Output is correct
10 Correct 839 ms 136264 KB Output is correct
11 Correct 519 ms 136756 KB Output is correct
12 Correct 513 ms 137044 KB Output is correct
13 Correct 59 ms 125488 KB Output is correct
14 Correct 232 ms 135292 KB Output is correct
15 Correct 132 ms 126724 KB Output is correct
16 Correct 862 ms 136556 KB Output is correct
17 Correct 493 ms 136800 KB Output is correct
18 Correct 606 ms 136732 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 125412 KB Output is correct
2 Correct 72 ms 125560 KB Output is correct
3 Correct 59 ms 125480 KB Output is correct
4 Correct 71 ms 125664 KB Output is correct
5 Correct 67 ms 125740 KB Output is correct
6 Correct 84 ms 125696 KB Output is correct
7 Correct 58 ms 125508 KB Output is correct
8 Correct 316 ms 135244 KB Output is correct
9 Correct 386 ms 130772 KB Output is correct
10 Correct 885 ms 136316 KB Output is correct
11 Correct 604 ms 136732 KB Output is correct
12 Correct 575 ms 137040 KB Output is correct
13 Correct 58 ms 125504 KB Output is correct
14 Correct 238 ms 135184 KB Output is correct
15 Correct 110 ms 126620 KB Output is correct
16 Correct 1030 ms 136548 KB Output is correct
17 Correct 520 ms 136724 KB Output is correct
18 Correct 485 ms 136724 KB Output is correct
19 Correct 1591 ms 153864 KB Output is correct
20 Correct 1624 ms 150472 KB Output is correct
21 Correct 1667 ms 152948 KB Output is correct
22 Correct 1507 ms 150520 KB Output is correct
23 Correct 1562 ms 150504 KB Output is correct
24 Correct 1540 ms 150548 KB Output is correct
25 Correct 1445 ms 150496 KB Output is correct
26 Correct 1493 ms 152976 KB Output is correct
27 Correct 1468 ms 152972 KB Output is correct
28 Correct 1510 ms 150448 KB Output is correct
29 Correct 1502 ms 150496 KB Output is correct
30 Correct 1579 ms 150468 KB Output is correct