Submission #309218

#	Time	Username	Problem	Language	Result	Execution time	Memory
309218		jainbot27	Wall (IOI14_wall)	C++17	0 / 100	1319 ms	14960 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 node NEUTRAL_ELEMENT = 0;
    const lzy NO_OPERATION = {-1<<50, -1<<50};
    const node START_VAL = 0;
    ll query_op(node a, node b, int len, int t){
        // cout << a << " " << b << " " << len << " " << t << endl;
        if(b==NO_OPERATION.f) return a;
        if(a==NO_OPERATION.f) return b;
        if(t==0) a=max(a, b);
        else a=min(a,b);
        return a;
    }
    ll calc_op(node a, node b){
        return max(a,b);
    }
    void apply_mod_op(node & a, node b, int c, int t){
        a = query_op(a, b, c, t);
    }
    void apply_mod_op(lzy&a, lzy b, int len, int t){
        a.f =query_op(a.f, b.f, len, 0);
        a.s =query_op(a.s, b.s, len, 1);
    }
    void apply_mod_op(node&a, lzy b, int len, int t){
        a=query_op(a, b.f, len, 0);
        a=query_op(a, b.s, len, 1);
    }
    void apply_mod_op(lzy&a, node b, int len, int t){
        if(t==0) a.f=query_op(a.f, b, len, 0);
        if(t==1) a.s=query_op(a.f, b, len, 1);
    }
    void propogate(int x, int lx, int rx){
        if(rx - lx == 1) return;
        int m = (lx + rx)/2;
        apply_mod_op(operations[2*x+1], operations[x], 1, 0);
        apply_mod_op(vals[2*x+1], operations[x], m-lx, 0);
        apply_mod_op(operations[2*x+2], operations[x], 1, 0);
        apply_mod_op(vals[2*x+2], operations[x], rx-m, 0);
        operations[x] = NO_OPERATION;
    }
    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        operations.assign(2 * size, {-1LL<<50, -1LL<<50});
        vals.assign(2 * size, 0);
    }
    void update(int l, int r, node v, int x, int lx, int rx, int t){
        propogate(x, lx, rx);
        if(lx >= r || l >= rx) return;
        if(lx >= l && rx <= r){
            apply_mod_op(operations[x], v, 1, t);
            apply_mod_op(vals[x], v, rx - lx, t);
            return;
        }
        int m = (lx + rx)/2;
        update(l, r, v, 2 * x + 1, lx , m, t);
        update(l, r, v, 2 * x + 2, m , rx, t);
        vals[x] = calc_op(vals[x * 2 + 1], vals[x * 2 + 2]);
    }
    void update(int l, int r, ll v, int t){
        update(l, r, v, 0, 0, size, t);
    }
    node query(int l, int r, int x, int lx, int rx){
        propogate(x, lx, rx);
        if(lx >= r || l >= rx) return NEUTRAL_ELEMENT;
        if(lx >= l && rx <= r){
            return vals[x];
        }
        int m = (lx + rx)/2;
        node m1 = query(l, r, 2 * x + 1, lx, m);
        node m2 = query(l, r, 2 * x + 2, m, rx);
        return calc_op(m1, m2);
    }
    node query(int l , int r){
        return query(l, 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, height[i], op[i]-1);
        // F0R(j, n){
        //     cout << st.query(j, j + 1) << nl;
        // }
        // cout << "NEW\n";
    }
    F0R(i, n){
        finalheight[i] = st.query(i, i+1);
    }
    return;
}

// int main(){
//     int op[] = {1, 2, 2, 1, 1, 2};
//     int height[] = {4, 1, 5, 3, 5, 0};
//     int left[] = {1, 4, 3, 0, 2, 6};
//     int right[] = {8, 9, 6, 5, 2, 7};
//     int n = 10;
//     int k = 6;
//     int finalheight[10];
//     buildWall(n, k, op, left, right, height, finalheight);
//     F0R(i, n){
//         cout << finalheight[i] << nl;
//     }
// }

Compilation message (stderr)

wall.cpp:41:35: warning: left shift count >= width of type [-Wshift-count-overflow]
   41 |     const lzy NO_OPERATION = {-1<<50, -1<<50};
      |                                   ^~
wall.cpp:41:43: warning: left shift count >= width of type [-Wshift-count-overflow]
   41 |     const lzy NO_OPERATION = {-1<<50, -1<<50};
      |                                           ^~

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