oj.uz

Submission #307358

# Submission time Handle Problem Language Result Execution time Memory
307358 2020-09-28T00:23:14 Z aZvezda Wall (IOI14_wall) C++14
100 / 100
 971 ms 222124 KB 
#include "wall.h"

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(labs(x) >= mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const ll MAX_N = 2e6 + 10;

struct Node {
    ll mn, mx, lazy;
    Node(ll a) {
        mn = mx = a;
        lazy = -1;
    }
    Node() {
        mn = mod;
        mx = -1;
        lazy = -1;
    }
};

Node operator +(const Node &a, const Node &b) {
    Node ret;
    ret.mn = min(a.mn, b.mn);
    ret.mx = max(a.mx, b.mx);
    return ret;
}

Node tree[4 * MAX_N];

void push(ll curr, ll l, ll r) {
    if(tree[curr].lazy == -1) {return;}
    tree[curr].mn = tree[curr].mx = tree[curr].lazy;
    if(l != r) {
        tree[curr * 2].lazy = tree[curr].lazy;
        tree[curr * 2 + 1].lazy = tree[curr].lazy;
    }
    tree[curr].lazy = -1;
}

void updAdding(ll curr, ll l, ll r, ll ql, ll qr, ll k) {
    push(curr, l, r);
    if(ql <= l && r <= qr && tree[curr].mx <= k) {
        tree[curr].lazy = k;
        push(curr, l, r);
        return;
    } else if(l > qr || r < ql || tree[curr].mn >= k) {return;}
    ll m = (l + r) / 2ll;
    updAdding(curr * 2, l, m, ql, qr, k);
    updAdding(curr * 2 + 1, m + 1, r, ql, qr, k);
    tree[curr] = tree[curr * 2] + tree[curr * 2 + 1];
}

void updRemoving(ll curr, ll l, ll r, ll ql, ll qr, ll k) {
    push(curr, l, r);
    if(ql <= l && r <= qr && tree[curr].mn >= k) {
        tree[curr].lazy = k;
        push(curr, l, r);
        return;
    } else if(l > qr || r < ql || tree[curr].mx <= k) {return;}
    ll m = (l + r) / 2ll;
    updRemoving(curr * 2, l, m, ql, qr, k);
    updRemoving(curr * 2 + 1, m + 1, r, ql, qr, k);
    tree[curr] = tree[curr * 2] + tree[curr * 2 + 1];
}

int ret[MAX_N], tme = 0;

void pushAll(ll curr, ll l, ll r) {
    push(curr, l, r);
    if(l == r) {
        ret[tme ++] = tree[curr].mn;
        return;
    }
    ll m = (l + r) / 2ll;
    pushAll(curr * 2, l, m);
    pushAll(curr * 2 + 1, m + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    tree[1].lazy = 0;
    for(ll i = 0; i < k; i ++) {
        if(op[i] == 1) {
            updAdding(1, 0, n - 1, left[i], right[i], height[i]);
        } else {
            updRemoving(1, 0, n - 1, left[i], right[i], height[i]);
        }
    }
    pushAll(1, 0, n - 1);
    for(int i = 0; i < n; i ++) {
        finalHeight[i] = ret[i];
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 188152 KB Output is correct
2 Correct 108 ms 188408 KB Output is correct
3 Correct 105 ms 188196 KB Output is correct
4 Correct 109 ms 188408 KB Output is correct
5 Correct 108 ms 188408 KB Output is correct
6 Correct 112 ms 188408 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 188152 KB Output is correct
2 Correct 270 ms 196088 KB Output is correct
3 Correct 202 ms 191608 KB Output is correct
4 Correct 343 ms 197180 KB Output is correct
5 Correct 325 ms 197496 KB Output is correct
6 Correct 355 ms 197628 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 188152 KB Output is correct
2 Correct 108 ms 188280 KB Output is correct
3 Correct 107 ms 188156 KB Output is correct
4 Correct 110 ms 188408 KB Output is correct
5 Correct 110 ms 188408 KB Output is correct
6 Correct 110 ms 188404 KB Output is correct
7 Correct 107 ms 188152 KB Output is correct
8 Correct 266 ms 196088 KB Output is correct
9 Correct 201 ms 191736 KB Output is correct
10 Correct 338 ms 196988 KB Output is correct
11 Correct 322 ms 197624 KB Output is correct
12 Correct 353 ms 197496 KB Output is correct
13 Correct 105 ms 188124 KB Output is correct
14 Correct 274 ms 196088 KB Output is correct
15 Correct 137 ms 188920 KB Output is correct
16 Correct 750 ms 197496 KB Output is correct
17 Correct 457 ms 197240 KB Output is correct
18 Correct 460 ms 197368 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 188152 KB Output is correct
2 Correct 106 ms 188284 KB Output is correct
3 Correct 105 ms 188152 KB Output is correct
4 Correct 111 ms 188408 KB Output is correct
5 Correct 109 ms 188408 KB Output is correct
6 Correct 115 ms 188408 KB Output is correct
7 Correct 106 ms 188152 KB Output is correct
8 Correct 269 ms 196088 KB Output is correct
9 Correct 198 ms 191608 KB Output is correct
10 Correct 336 ms 197112 KB Output is correct
11 Correct 320 ms 197704 KB Output is correct
12 Correct 354 ms 197624 KB Output is correct
13 Correct 109 ms 188152 KB Output is correct
14 Correct 280 ms 196152 KB Output is correct
15 Correct 137 ms 188920 KB Output is correct
16 Correct 741 ms 197368 KB Output is correct
17 Correct 458 ms 197240 KB Output is correct
18 Correct 458 ms 197368 KB Output is correct
19 Correct 971 ms 222076 KB Output is correct
20 Correct 933 ms 219640 KB Output is correct
21 Correct 940 ms 222024 KB Output is correct
22 Correct 938 ms 219604 KB Output is correct
23 Correct 939 ms 219644 KB Output is correct
24 Correct 935 ms 219640 KB Output is correct
25 Correct 946 ms 219640 KB Output is correct
26 Correct 941 ms 222124 KB Output is correct
27 Correct 948 ms 222072 KB Output is correct
28 Correct 936 ms 219504 KB Output is correct
29 Correct 939 ms 219596 KB Output is correct
30 Correct 928 ms 219640 KB Output is correct