Submission #1149706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149706		Lib	Wall (IOI14_wall)	C++20	100 / 100	478 ms	78888 KiB

wall

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

 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int INF = 1e9 + 69;

struct SegmentTree{
    int n;
    vector<pair<int, int>> a;

    SegmentTree(int _n){
        n = _n;
        a.resize(n * 4 + 4, {0, 0});
    }

    void apply(int id, pair<int, int> x){
        maximize(a[id].first, x.first);
        maximize(a[id].second, x.first);
        minimize(a[id].first, x.second);
        minimize(a[id].second, x.second);
    }

    void down(int id){
        apply(id * 2, a[id]);
        apply(id * 2 + 1, a[id]);
        a[id] = {0, INF};
    }

    void update(int u, int v, pair<int, int> val, int l, int r, int id){
        if (u <= l && r <= v) {
            apply(id, val);
            return;
        }
        if (a[id] != make_pair(0, INF)) down(id);
        int mid = (l + r) >> 1;
        if (u <= mid) update(u, v, val, l, mid, id * 2);
        if (v > mid) update(u, v, val, mid + 1, r, id * 2 + 1);
    }

    void update(int u, int v, pair<int, int> val){update(u, v, val, 0, n-1, 1);}

    int get(int i){
        int l = 0, r = n - 1, id = 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if (a[id] != make_pair(0, INF)) down(id);
            if (i <= mid) {
                r = mid;
                id = id * 2;
            }
            else{
                l = mid + 1;
                id = id * 2 + 1;
            }
        }
        return a[id].first;
    }
};


void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    SegmentTree st(n);
    for(int i = 0; i<k; ++i) {
      if (op[i] == 1) st.update(left[i], right[i], make_pair(height[i], INF));
      else st.update(left[i], right[i], make_pair(0, height[i]));
    }
    for(int i= 0; i<n; ++i) finalHeight[i] = st.get(i);
}

// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int n, q; cin >> n >> q;
//     SegmentTree st(n);
//     for(int i = 0; i<q; ++i){
//         int op, l, r, h; cin >> op >> l >> r >> h;
//         if (op == 1) st.update(l, r, {h, INF});
//         else st.update(l, r, {0, h});
//     }
//     for(int i = 0; i < n; ++i) cout << st.get(i) << " "; 
//     cout << "\n";


//     return 0;
// }

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