oj.uz

Submission #1039805

# Submission time Handle Problem Language Result Execution time Memory
1039805 2024-07-31T09:31:51 Z daoda Wall (IOI14_wall) C++17
100 / 100
 497 ms 162156 KB 
#include "wall.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(x, a, b) for(ll x=a;x < ll(b); x++)
#define endl '\n'
#define TESTCASE ll t; cin >> t; for(ll T=0; T < t; T++)

using namespace std;
// using namespace __gnu_pbds;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<short> vs;
typedef long double ld;

// template <class T>
// using Tree = 
    // tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll INF = ll(1e9) + 10;
const ll INIT = 7;
const ll MAX_VAL = 50;
const ll MAX_SZ = (ll) 1e4;
const ll MAX_N = 2e6;
const ll MAX_M = MAX_N;
const long double eps = 1e-4;
const ll MOD = ll(1e9) + 7;

vi rd = {0, 1, 0, -1}, cd = {1, 0, -1, 0};

ll add(ll a, ll b) {
    return ((a % MOD) + (b % MOD) + 2ll * MOD) % MOD;
}

ll mult(ll a, ll b) {
    return (((a % MOD) * (b % MOD)) + MOD) % MOD;
}

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

int n, k, *op, *left_arr, *right_arr, *height, *finalHeight; 

struct Node {
    int lb = 0, upb = 0, strt, sz;
};

Node tree[MAX_N << 2];
ll tree_sz;

//push down information from current node to another. if current node is reset, assume that all data in other node is faulty

pi sync(int lb1, int upb1, int lb2, int upb2) {
    if(upb1 <= lb2) return make_pair(lb2, lb2);
    else if(lb1 >= upb2) return make_pair(upb2, upb2);
    else return make_pair(max(lb1, lb2), min(upb1, upb2));
}

int check(int strt, int end, int tl, int tr) {
    if(tl > tr) return -1;
    else if(tl >= strt && tr <= end) return 0;
    else if(tl > end || tr < strt) return 1;
    else return 2;
}

void reset(int node) {
    tree[node].lb = 0;
    tree[node].upb = INF;
}

void init(int num_ele) {
    tree_sz = 1;
    while(tree_sz < (num_ele << 1)) tree_sz <<= 1;

    for(int i = tree_sz >> 1; i < tree_sz; i++) {
        tree[i].sz = 1;
        tree[i].strt = i - (tree_sz >> 1);
    }

    for(int i = (tree_sz >> 1) - 1; i >= 1; i--) {
        tree[i].sz = tree[i << 1].sz << 1;
        tree[i].strt = tree[i << 1].strt;
    }
}

void pushdown(int from, int to) {
    auto res = sync(tree[to].lb, tree[to].upb, tree[from].lb, tree[from].upb);

    tree[to].lb = res.first;
    tree[to].upb = res.second;
}

//type = 1 indicates that you want to increment the value, type = 2 is reset

void update_vals(int strt, int end, int cur, int lb, int upb) {
    int res = check(strt, end, tree[cur].strt, tree[cur].strt + tree[cur].sz - 1);

    if(res == 1) return;
    if(!res) {
        auto [next_lb, next_upb] = sync(tree[cur].lb, tree[cur].upb, lb, upb);

        tree[cur].lb = next_lb;
        tree[cur].upb = next_upb;
        return;
    }

    pushdown(cur, cur << 1);
    pushdown(cur, (cur << 1) + 1);

    reset(cur); 

    update_vals(strt, end, cur << 1, lb, upb);
    update_vals(strt, end, (cur << 1) + 1, lb, upb);
}

int point_query(int loc) {
    loc += tree_sz >> 1; 
        
    int cur_h = tree[loc].lb;

    while(loc != 1) {
        loc >>= 1;

        if(tree[loc].lb > cur_h) cur_h = tree[loc].lb;
        else if(tree[loc].upb < cur_h) cur_h = tree[loc].upb;
    }

    return cur_h;
}

void buildWall(int p1, int p2, int* p3, int* p4, int* p5, int*p6, int*p7) {
    n = p1; k = p2; op = p3; left_arr = p4; right_arr = p5; height = p6; finalHeight = p7;

    init(n);

    FOR(i, 0, k) {
        if(op[i] == 1) update_vals(left_arr[i], right_arr[i], 1, height[i], INF);
        else update_vals(left_arr[i], right_arr[i], 1, 0, height[i]);
    }

    FOR(i, 0, n) {
        finalHeight[i] = point_query(i);
        // cout << finalHeight[i] << " ";
    }
    // cout << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 125520 KB Output is correct
2 Correct 46 ms 125772 KB Output is correct
3 Correct 46 ms 125520 KB Output is correct
4 Correct 51 ms 125876 KB Output is correct
5 Correct 50 ms 125784 KB Output is correct
6 Correct 50 ms 125784 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 125524 KB Output is correct
2 Correct 134 ms 139160 KB Output is correct
3 Correct 196 ms 132696 KB Output is correct
4 Correct 370 ms 143700 KB Output is correct
5 Correct 217 ms 144728 KB Output is correct
6 Correct 225 ms 143192 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 125408 KB Output is correct
2 Correct 46 ms 125780 KB Output is correct
3 Correct 47 ms 125680 KB Output is correct
4 Correct 50 ms 125780 KB Output is correct
5 Correct 58 ms 125776 KB Output is correct
6 Correct 51 ms 125776 KB Output is correct
7 Correct 48 ms 125524 KB Output is correct
8 Correct 130 ms 139088 KB Output is correct
9 Correct 162 ms 132692 KB Output is correct
10 Correct 375 ms 143708 KB Output is correct
11 Correct 277 ms 144724 KB Output is correct
12 Correct 258 ms 143104 KB Output is correct
13 Correct 48 ms 125596 KB Output is correct
14 Correct 131 ms 139100 KB Output is correct
15 Correct 69 ms 126804 KB Output is correct
16 Correct 490 ms 144124 KB Output is correct
17 Correct 228 ms 143184 KB Output is correct
18 Correct 250 ms 143184 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125524 KB Output is correct
2 Correct 54 ms 125668 KB Output is correct
3 Correct 47 ms 125580 KB Output is correct
4 Correct 51 ms 125776 KB Output is correct
5 Correct 49 ms 125776 KB Output is correct
6 Correct 55 ms 125776 KB Output is correct
7 Correct 48 ms 125524 KB Output is correct
8 Correct 124 ms 139300 KB Output is correct
9 Correct 168 ms 132692 KB Output is correct
10 Correct 370 ms 143700 KB Output is correct
11 Correct 212 ms 144560 KB Output is correct
12 Correct 228 ms 143184 KB Output is correct
13 Correct 44 ms 125528 KB Output is correct
14 Correct 119 ms 139184 KB Output is correct
15 Correct 65 ms 126800 KB Output is correct
16 Correct 428 ms 143900 KB Output is correct
17 Correct 252 ms 143184 KB Output is correct
18 Correct 242 ms 143348 KB Output is correct
19 Correct 465 ms 162156 KB Output is correct
20 Correct 433 ms 159568 KB Output is correct
21 Correct 488 ms 161876 KB Output is correct
22 Correct 497 ms 159572 KB Output is correct
23 Correct 473 ms 159576 KB Output is correct
24 Correct 479 ms 159584 KB Output is correct
25 Correct 495 ms 159572 KB Output is correct
26 Correct 467 ms 161880 KB Output is correct
27 Correct 464 ms 162044 KB Output is correct
28 Correct 459 ms 159324 KB Output is correct
29 Correct 442 ms 159568 KB Output is correct
30 Correct 453 ms 159488 KB Output is correct