Submission #309244

#	Time	Username	Problem	Language	Result	Execution time	Memory
309244		jainbot27	Wall (IOI14_wall)	C++17	0 / 100	283 ms	8184 KiB

wall

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

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

using node = ll;
using lzy = pair<ll, ll>;
 
struct lazy{
    int size;
    vector<lzy> operations;
    vector<node> vals;
    const lzy NEUTRAL_ELEMENT = {1, infLL};
    const lzy NO_OPERATION = {-69, -69};
    void propogate(int x, int lx, int rx){
        if(operations[x] == NO_OPERATION) return;
        if(operations[x].f == 0) ckmax(vals[x], operations[x].s);
        else ckmin(vals[x], operations[x].s);
        if(rx - lx == 1) return;
        if(operations[2*x+1].f == 0) ckmax(vals[2*x+1], operations[2*x+1].s);
        else if(operations[2*x+1].f == 1)ckmin(vals[x*2+1], operations[2*x+1].s);
        if(operations[2*x+2].f == 0) ckmax(vals[2*x+2], operations[2*x+2].s);
        else if(operations[2*x+2].f == 1) ckmin(vals[x*2+2], operations[2*x+2].s);
        operations[2*x+1] = operations[x];
        operations[2*x+2] = operations[x];
        operations[x] = NO_OPERATION;
    }
    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        operations.assign(2 * size, NO_OPERATION);
        vals.assign(2 * size, 0);
        // build(0, 0, size);
    }
    void update(int l, int r, lzy v, int x, int lx, int rx){
        propogate(x, lx, rx);
        if(lx >= r || l >= rx) return;
        if(lx >= l && rx <= r){
            operations[x] = v;
            propogate(x, lx, rx);
            return;
        }
        int m = (lx + rx)/2;
        update(l, r, v, 2 * x + 1, lx , m);
        update(l, r, v, 2 * x + 2, m , rx);
    }
    void update(int l, int r, lzy v){
        update(l, r, v, 0, 0, size);
    }
    node query(int l, int x, int lx, int rx){
        propogate(x, lx, rx);
        if(lx + 1 == rx){
            assert(lx == l);
            return vals[x];
        }
        int m = (lx + rx)/2;
        if(l < m)
            return query(l, 2 * x + 1, lx, m);
        else
            return query(l, 2 * x + 2, m, rx);
    }
    node query(int r){
        return query(r, 0, 0, size);
    }
} st;


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalheight[]){
    st.init(n);
    F0R(i, k){
        st.update(left[i], right[i]+1, {op[i]-1, height[i]});
        // F0R(j, n){
        //     cout << st.query(j, j + 1) << nl;
        // }
        // cout << "NEW\n";
    }
    F0R(i, n){
        finalheight[i] = st.query(i);
    }
    return;
}

// int main(){
//     int n, k; 
//     cin >> n >> k;
//     vi op(k), left(k), right(k), height(k), finalheight(n, 0);
//     F0R(i, k) {
//         cin >> left[i] >> right[i] >> height[i] >> op[i];
//     }
//     buildWall(n, k, op, left, right, height, finalheight);
//     F0R(i, n){
//         cout << finalheight[i] << " ";
//     }
// }

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