Submission #1039805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039805		daoda	Wall (IOI14_wall)	C++17	100 / 100	497 ms	162156 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39