Submission #373199

#	Time	Username	Problem	Language	Result	Execution time	Memory
373199		Doxeno	Wall (IOI14_wall)	C++17	24 / 100	607 ms	38380 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],lz[MAXN*2];

void push_down(int pos){
    if(pos >= MAXN || lz[pos] == 0)return;
    lz[pos] = 0; lz[pos*2] = lz[pos*2+1] = 1;
    t[pos*2] = t[pos*2+1] = t[pos];
    if(m[pos*2] > mx[pos])t[pos*2] = 1;
    if(m[pos*2+1] > mx[pos])t[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] = max(m[pos*2],m[pos]);
    m[pos*2+1] = max(m[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);
        lz[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){
        mx[n] = max(mx[n],val);
        m[n] = max(m[n],val);
        lz[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] = t[MAXN+i]?mx[MAXN+i]:m[MAXN+i];
    }
}

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