Submission #585423

#	Time	Username	Problem	Language	Result	Execution time	Memory
585423		erto	Wall (IOI14_wall)	C++17	0 / 100	132 ms	13820 KiB

wall

#include <bits/stdc++.h>
typedef long long int ll;
#define INF ll(1e9 + 7)
#define INF2 998244353
#define N (ll)(1e5 + 5)
using namespace std;
//#define int ll
#define lsb(x) (x & (-x))
 
int n, g, h,m,  q,z,t1,t2, ans=0, ans2, n2, k, n3; 

int comb(int x, int y){
    return max(x, y);
}
 
struct SegTree{
    int n;
    vector<int> tree, tmax, tmin;
 
    SegTree(int _n){
        n = _n+1;
        while(lsb(n) != n)
            n += lsb(n);
        tree.resize(2*n, 0);
        tmax.resize(2*n, 0);
        tmin.resize(2*n, INF);
    }
 
    void update(int i, int val){
        i += n;
        tree[i] = val;
        while(i >>= 1){
            tree[i] = comb(tree[i * 2] , tree[i * 2 | 1]);
            
        }
    }

    void push(int i, int len){
        if(!len)return;
        if(tmin[i] != INF){
            tmin[i * 2 + 1] = tmin[i * 2] = tmin[i];
            tree[i * 2 + 1] = min(tmin[i], tree[i * 2 + 1]);
            tree[i * 2] = min(tmin[i], tree[i * 2]);
            tmin[i] = INF;
        }
        if(tmax[i]){
            tmax[i * 2 + 1] = tmax[i * 2] = tmax[i];
            tree[i * 2 + 1] = max(tmax[i], tree[i * 2 + 1]);
            tree[i * 2] = max(tmax[i], tree[i * 2]);
            tmax[i] = 0;
        }
    }

    void maxx(int v, int ql, int qr){maxx(1, v, 0, n - 1, ql, qr);}
    void maxx(int i, int v, int lb, int rb, int ql, int qr){
        if(lb > qr || rb < ql)return;
        if(ql <= lb && rb <= qr){
            if(tmin[i] != INF)tmin[i] = INF;
            tmax[i] = max(tmax[i], v);
            tree[i] = max(tree[i], v);
            return;
        }
        int md = (rb + lb) /2;
        push(i, rb - lb + 1);

        maxx(i * 2, v, lb, md, ql, qr);
        maxx(i * 2 + 1, v, md + 1, rb, ql, qr);
        //tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }   

    void minn(int v, int ql, int qr){minn(1, v, 0, n - 1, ql, qr);}
    void minn(int i, int v, int lb, int rb, int ql, int qr){
        if(lb > qr || rb < ql)return;
        if(ql <= lb && rb <= qr){
            if(tmax[i])tmax[i] = 0;
            tmin[i] = min(tmin[i], v);
            tree[i] = min(tree[i], v);
            return;
        }
        int md = (rb + lb) /2;
        push(i, rb - lb + 1);

        minn(i * 2, v, lb, md, ql, qr);
        minn(i * 2 + 1, v, md + 1, rb, ql, qr);
        //tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }   

    int qu(int ql, int qr){return qu(1, 0, n - 1, ql, qr);}
    int qu(int i, int lb, int rb, int ql, int qr){
        if(lb > qr || rb < ql)return - 1;
        if(ql <= lb && rb <= qr){
            return tree[i];
        }
        int md = (rb + lb) /2;
        push(i, rb - lb + 1);

        return max(qu(i * 2, lb, md, ql, qr), qu(i * 2 + 1, md + 1, rb, ql, qr));
        //tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }   


};  

void buildWall(int n, int k, int op[], int le[], int ri[], int height[], int finalHeight[]){
    SegTree s(n + 1);
    for(int i=0; i<k; i++){
        if(op[i] == 1){
            s.maxx(height[i], le[i], ri[i]);
        }
        else{
            s.minn(height[i], le[i], ri[i]);
        }
    }

    for(int i=0; i<n; i++){
        finalHeight[i] = s.qu(i, i);
    }
}

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