Submission #1184759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184759		countless	Wall (IOI14_wall)	C++20	100 / 100	711 ms	214284 KiB

wall

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

typedef long long ll;
typedef long double ld;

const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-12;

#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<int>(a, b)(rng);
// shuffle(all(a), rng);

struct segtree {
    int l, r;
    segtree *left, *right;
    int down, up;

    void merge() {
        ;; // nothing??
    }

    void update(pair<int, int> upd) {
        down = max(down, upd.first);
        up = max(up, down);

        up = min(up, upd.second);
        down = min(down, up);
    }

    segtree(int l, int r) : l(l), r(r) {
        down = 0;
        up = INT_MAX;

        if (l == r) {
            left = right = nullptr;
            return;
        }

        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
        merge();
    }

    void propagate() {
        if (left) {
            left->update({down, up});
            right->update({down, up});
            down = 0;
            up = INT_MAX;
        }
    }

    int query(int ind) {
        if (l == r) {
            return down;
        }

        int m = (l+r)/2;
        propagate();
        if (ind <= m) return left->query(ind);
        else return right->query(ind);
    }

    void updateUp(int ql, int qr, int upd) {
        if (ql > r || qr < l) return;

        if (ql <= l && r <= qr) {
            update({0, upd});
            propagate();
            return;
        }

        int m = (l+r)/2;
        propagate();
        left->updateUp(ql, qr, upd);
        right->updateUp(ql, qr, upd);
    }

    void updateDown(int ql, int qr, int upd) {
        if (ql > r || qr < l) return;

        if (ql <= l && r <= qr) {
            update({upd, INT_MAX});
            propagate();
            return;
        }
        
        int m = (l+r)/2;
        propagate();
        left->updateDown(ql, qr, upd);
        right->updateDown(ql, qr, upd);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    segtree st(0, n-1);

    REP(i, 0, k) {
        if (op[i] == 1) {
            st.updateDown(left[i], right[i], height[i]);
        }

        else {
            st.updateUp(left[i], right[i], height[i]);
        }
    }

    // this should be an insignificant until subtask 3, optimize by storing nodes later:P
    REP(i, 0, n) {
        finalHeight[i] = st.query(i);
        // cerr << st.query(i) << endl;
    }
    return;
}

// signed main() {
//     int n, k; cin >> n >> k;
//     int op[k], left[k], right[k], height[k], finalHeight[n];
//     fill_n(finalHeight, n, 0);
//     REP(i, 0, k) {
//         cin >> op[i] >> left[i] >> right[i] >> height[i];
//     }

//     buildWall(n, k, op, left, right, height, finalHeight);

//     for (auto &x : finalHeight) {
//         cout << x << endl;
//     }
//     cout << endl;
// }

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