Submission #879705

#	Time	Username	Problem	Language	Result	Execution time	Memory
879705		AlphaMale06	Wall (IOI14_wall)	C++14	100 / 100	880 ms	102228 KiB

wall

#include<bits/stdc++.h>

#include "wall.h"
using namespace std;
const int N = 2e6+3;
int mn[4*N], mx[4*N], f[4*N];
int inf=100000001;

void inter(int a, int b, int c, int d, int &lft, int &rgt){
    if(a>d){
        lft=rgt=a;
    }
    else if(b<c){
        lft=rgt=b;
    }
    else{
        lft=max(a, c);
        rgt=min(b, d);
    }
}

void Push(int node){
    int lc=2*node+1;
    int rc=2*node+2;
    inter(mx[node], mn[node], mx[lc], mn[lc], mx[lc], mn[lc]);
    inter(mx[node], mn[node], mx[rc], mn[rc], mx[rc], mn[rc]);
    f[lc]=f[rc]=f[node];
    mn[node]=inf;
    mx[node]=0;
}

void mxUpd(int node, int l, int r, int L, int R, int val){
    if(l>r || l>R | r<L)return;
    if(l>=L && r<=R){
        inter(val, inf, mx[node], mn[node], mx[node], mn[node]);
        if(mn[node]==inf)f[node]=0;
        else f[node]=1;
        return;
    }
    Push(node);
    int mid=(l+r)/2;
    mxUpd(2*node+1, l, mid, L, R, val);
    mxUpd(2*node+2, mid+1, r, L, R, val);
}

void mnUpd(int node, int l, int r, int L, int R, int val){
    if(l>r || l>R || r<L)return;
    if(l>=L && r<=R){
        inter(0, val, mx[node], mn[node], mx[node], mn[node]);
        if(mx[node]==0)f[node]=1;
        else f[node]=0;
        return;
    }
    Push(node);
    int mid=(l+r)/2;
    mnUpd(2*node+1, l, mid, L, R, val);
    mnUpd(2*node+2, mid+1, r, L, R, val);
}
int Get(int node, int l, int r, int ind){
    if(l>ind || r<ind)return 0;
    if(l==r){
        if(f[node])return max(mx[node], mn[node]);
        else return min(mn[node], mx[node]);
    }
    Push(node);
    int mid=(l+r)/2;
    return Get(2*node+1, l, mid, ind)+Get(2*node+2, mid+1, r, ind);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=0; i<4*N; i++)mn[i]=inf;
    for(int i=0; i< k; i++){
        if(op[i]==1){
            mxUpd(0, 0, n-1, left[i], right[i], height[i]);
        }
        else{
            mnUpd(0, 0, n-1, left[i], right[i], height[i]);
        }
    }
    for(int i=0; i< n; i++){
        finalHeight[i]=Get(0, 0, n-1, i);
    }
    return;
}

Compilation message (stderr)

wall.cpp: In function 'void mxUpd(int, int, int, int, int, int)':
wall.cpp:33:16: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   33 |     if(l>r || l>R | r<L)return;
      |               ~^~

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