Submission #697944

#	Time	Username	Problem	Language	Result	Execution time	Memory
697944		BhavayGoyal	Wall (IOI14_wall)	C++14	100 / 100	897 ms	65588 KiB

wall

#include <bits/stdc++.h>
#include <wall.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

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

#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};


// -------------------------------------------------- Main Code --------------------------------------------------

struct Node {
    int val, mn, mx; // final value, last was delete oper, last was add oper
};

struct segTree {
    int n;
    vector<Node> tree;

    segTree(int N) {n = 1; while (n < N) n *= 2; tree = vector<Node>(2*n+2, {0, inf, -1});}

    void propogate(int node, int left, int right) {
        if (tree[node].mn == inf && tree[node].mx == -1) return;

        if (tree[node].mn != inf) {
            tree[node].val = min(tree[node].val, tree[node].mn);
            if (left != right) {
                tree[node*2].mx = min(tree[node].mn, tree[node*2].mx);
                tree[node*2].mn = min(tree[node].mn, tree[node*2].mn);
                tree[node*2+1].mx = min(tree[node].mn, tree[node*2+1].mx);
                tree[node*2+1].mn = min(tree[node].mn, tree[node*2+1].mn);
            }
            tree[node].mn = inf;
        }
        if (tree[node].mx != -1) {
            tree[node].val = max(tree[node].val, tree[node].mx);
            if (left != right) {
                tree[node*2].mn = max(tree[node].mx, tree[node*2].mn);
                tree[node*2].mx = max(tree[node].mx, tree[node*2].mx);
                tree[node*2+1].mn = max(tree[node].mx, tree[node*2+1].mn);
                tree[node*2+1].mx = max(tree[node].mx, tree[node*2+1].mx);
            }
            tree[node].mx = -1;
        }
    }

    void update(int node, int left, int right, int l, int r, int val, int type) {
        propogate(node, left, right);
        if (left > r || right < l) return;
        else if (left >= l && right <= r) {
            if (type == 1) {
                // add operation
                tree[node].mn = inf;
                tree[node].mx = val;
            }
            else {
                // delete operation
                tree[node].mn = val;
                tree[node].mx = -1;
            }
            propogate(node, left, right);
            return;
        }
        update(node*2, left, (left+right)/2, l, r, val, type);
        update(node*2+1, (left+right)/2+1, right, l, r, val, type);
    }
    void update(int l, int r, int val, int type) {update(1, 1, n, l, r, val, type);}

    int query(int node, int left, int right, int idx) {
        propogate(node, left, right);
        if (left == right) {
            return tree[node].val;
        }
        int mid = (left+right)/2;
        if (idx <= mid) return query(node*2, left, (left+right)/2, idx);
        else return query(node*2+1, (left+right)/2+1, right, idx);
    }
    int query(int idx) {return query(1, 1, n, idx);}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    segTree tree(n);
    for (int i = 0; i < k; i++) tree.update(left[i]+1, right[i]+1, height[i], op[i]);
    for (int i = 0; i < n; i++) finalHeight[i] = tree.query(i+1);
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39