Submission #373205

#	Time	Username	Problem	Language	Result	Execution time	Memory
373205		Doxeno	Wall (IOI14_wall)	C++17	24 / 100	655 ms	44140 KiB

wall

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2097152;
int m[2*MAXN], mx[2*MAXN],h[2*MAXN],t[2*MAXN],lzx[MAXN*2],lzm[MAXN*2];

void push_down(int pos){
    if(pos >= MAXN)return;
    t[2*pos] = t[2*pos+1] = t[pos];
    if(lzx[pos]){
        lzx[pos] = 0; lzx[pos*2] = lzx[pos*2+1] = 1;
        mx[pos*2] = min(mx[pos*2],mx[pos]);
        mx[pos*2+1] = min(mx[pos*2+1],mx[pos]);
        m[pos*2] = min(m[pos*2],mx[pos]);
        m[pos*2+1] = min(m[pos*2+1],mx[pos]);
    }
    if(lzm[pos]){
        lzm[pos] = 0; lzm[pos*2] = lzm[pos*2+1] = 1;
        m[pos*2] = max(m[pos*2],m[pos]);
        m[pos*2+1] = max(m[pos*2+1],m[pos]);
        mx[pos*2] = max(mx[pos*2],m[pos]);
        mx[pos*2+1] = max(mx[pos*2+1],m[pos]);
    }
}

void upx(int l, int r, int ql, int qr, int n, int val){
    if(l >= qr || r <= ql)return;
    if(l >= ql && r <= qr){
        if(val <= m[n])t[n]=1;
        mx[n] = min(mx[n],val);
        m[n] = min(m[n],val);
        lzx[n] = 1;
        return;
    }
    push_down(n);
    upx(l,(l+r)/2,ql,qr,2*n,val);
    upx((l+r)/2,r,ql,qr,2*n+1,val);
}

void upm(int l, int r, int ql, int qr, int n, int val){
    if(l >= qr || r <= ql)return;
    if(l >= ql && r <= qr){
        if(val >= mx[n])t[n] = 0;
        mx[n] = max(mx[n],val);
        m[n] = max(m[n],val);
        lzm[n] = 1;
        return;
    }
    push_down(n);
    upm(l,(l+r)/2,ql,qr,2*n,val);
    upm((l+r)/2,r,ql,qr,2*n+1,val);
}


void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
    for(int i = 0; i < MAXN*2; i++)mx[i] = 1000000000;
    for(int i = 0; i < k; i++){
        if(op[i] == 1)upm(0,MAXN,left[i],right[i]+1,1,height[i]);
        else upx(0,MAXN,left[i],right[i]+1,1,height[i]);
    }
    for(int i = 1; i < MAXN; i++)push_down(i);
    for(int i = 0; i < n; i++){
    //    cout << mx[MAXN+i] << " " << m[MAXN+i]<<endl;
        finalHeight[i] = m[MAXN+i];
    }
}

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