Submission #585428

#	Time	Username	Problem	Language	Result	Execution time	Memory
585428		erto	Wall (IOI14_wall)	C++17	0 / 100	154 ms	8064 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> tmax, tmin;
 
    SegTree(int _n){
        n = _n+1;
        while(lsb(n) != n)
            n += lsb(n);
        tmax.resize(2*n, 0);
        tmin.resize(2*n, INF);
    }
 

    void push(int i, int len){
        if(!len)return;
        if(tmin[i] != INF){
            tmin[i * 2 + 1] = min(tmin[i * 2 + 1], tmin[i]);
            tmax[i * 2 + 1] = min(tmin[i * 2 + 1], tmax[i * 2 + 1]);
            tmin[i * 2] = min(tmin[i * 2], tmin[i]);
            tmax[i * 2] = min(tmin[i * 2], tmax[i * 2]);
            tmin[i] = INF;
        }
        if(tmax[i]){
            tmax[i * 2 + 1] = max(tmax[i * 2], tmax[i]);
            tmin[i * 2 + 1] = max(tmin[i * 2 + 1], tmax[i * 2 + 1]);
            tmax[i * 2] = max(tmax[i * 2], tmax[i]);
            tmin[i * 2] = max(tmin[i * 2], tmax[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);
            tmin[i] = max(tmin[i], tmax[i]);
            return;
        }
        int md = (rb + lb) /2;
        push(i, (rb - lb + 1) / 2);

        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);
            tmax[i] = min(tmax[i], tmin[i]);
            return;
        }
        int md = (rb + lb) /2;
        push(i, (rb - lb + 1) / 2);

        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 i){
        int t1=0;
        i+=n;
        while(i){
            t1 = min(t1, tmin[i]);
            t1 = max(t1, tmax[i]);
            i /= 2;
        }
        return t1;
    }
};  

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);
    }
    return;
}

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