Submission #653717

#	Time	Username	Problem	Language	Result	Execution time	Memory
653717		Lobo	Wall (IOI14_wall)	C++17	24 / 100	563 ms	25924 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
const int inf = 1e9+10;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

int n, a[maxn], trmn1[4*maxn],trmn2[4*maxn],trmx1[4*maxn],trmx2[4*maxn], lzadd[4*maxn], lzrem[4*maxn];

void build(int no, int l, int r) {
    lzadd[no] = lzrem[no] = -1;
    if(l == r) {
        trmn1[no] = trmn2[no] = trmx1[no] = trmx2[no] = a[l]; return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    build(f1,l,mid);
    build(f2,mid+1,r);
    trmn1[no] = min(trmn1[f1],trmn1[f2]);
    trmn2[no] = min(trmn2[f1],trmn2[f2]);
    if(trmn1[no] != trmn1[f1]) trmn2[no] = min(trmn2[no],trmn1[f1]);
    if(trmn1[no] != trmn1[f2]) trmn2[no] = min(trmn2[no],trmn1[f2]);
}
void flush(int no, int l, int r) {
    if(lzadd[no] != -1) {
        trmn1[no] = max(trmn1[no],lzadd[no]); 
        trmn2[no] = max(trmn2[no],lzadd[no]);
        trmx1[no] = max(trmx1[no],lzadd[no]);
        trmx2[no] = max(trmx2[no],lzadd[no]);
        if(l != r) {
            int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
            if(lzadd[f1] == -1) lzadd[f1] = lzadd[no];
            else lzadd[f1] = max(lzadd[f1],lzadd[no]);
            if(lzrem[f1] == -1 || lzadd[no] > lzrem[f1]) 
                lzrem[f1] = -1;

            if(lzadd[f2] == -1) lzadd[f2] = lzadd[no];
            else lzadd[f2] = max(lzadd[f2],lzadd[no]);
            if(lzrem[f2] == -1 || lzadd[no] > lzrem[f2]) 
                lzrem[f2] = -1;
        }
        lzadd[no] = -1;
    }
    if(lzrem[no] != -1) {
        trmn1[no] = min(trmn1[no],lzadd[no]); 
        trmn2[no] = min(trmn2[no],lzadd[no]);
        trmx1[no] = min(trmx1[no],lzadd[no]);
        trmx2[no] = min(trmx2[no],lzadd[no]);
        if(l != r) {
            int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
            if(lzrem[f1] == -1) lzrem[f1] = lzrem[no];
            else lzrem[f1] = min(lzrem[f1],lzrem[no]);
            if(lzadd[f1] == -1 || lzrem[no] < lzadd[f1]) 
                lzadd[f1] = -1;

            if(lzrem[f2] == -1) lzrem[f2] = lzrem[no];
            else lzrem[f2] = min(lzrem[f2],lzrem[no]);
            if(lzadd[f2] == -1 || lzrem[no] < lzadd[f2]) 
                lzadd[f2] = -1;
        }
        lzrem[no] = -1;
    }
}
//a[i] = max(a[i],val)
void attadd(int no, int l, int r, int L, int R, int val) {
    flush(no,l,r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        trmx1[no] = max(trmx1[no],val);
        trmx2[no] = max(trmx2[no],val);
        if(l == r) {
            trmn1[no] = max(trmn1[no],val);
            trmn2[no] = max(trmn1[no],val);
            return;
        }
        if(trmn1[no] >= val) return;
        if(trmn2[no] > val) {
            lzadd[no] = val;
            flush(no,l,r);
            return;
        }
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    attadd(f1,l,mid,L,R,val);
    attadd(f2,mid+1,r,L,R,val);
    trmn1[no] = min(trmn1[f1],trmn1[f2]);
    trmn2[no] = min(trmn2[f1],trmn2[f2]);
    if(trmn1[no] != trmn1[f1]) trmn2[no] = min(trmn2[no],trmn1[f1]);
    if(trmn1[no] != trmn1[f2]) trmn2[no] = min(trmn2[no],trmn1[f2]);
}

void attrem(int no, int l, int r, int L, int R, int val) {
    flush(no,l,r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        trmn1[no] = min(trmn1[no],val);
        trmn2[no] = min(trmn2[no],val);
        if(l == r) {
            trmx1[no] = min(trmx1[no],val);
            trmx2[no] = min(trmx1[no],val);
            return;
        }
        if(trmx1[no] <= val) return;
        if(trmx2[no] < val) {
            lzrem[no] = val;
            flush(no,l,r);
            return;
        }
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    attrem(f1,l,mid,L,R,val);
    attrem(f2,mid+1,r,L,R,val);
    trmx1[no] = max(trmx1[f1],trmx1[f2]);
    trmx2[no] = max(trmx2[f1],trmx2[f2]);
    if(trmn1[no] != trmn1[f1]) trmn2[no] = max(trmn2[no],trmn1[f1]);
    if(trmn1[no] != trmn1[f2]) trmn2[no] = max(trmn2[no],trmn1[f2]);
}

void findans(int no, int l, int r) {
    flush(no,l,r);
    if(l == r) {
        a[l] = trmx1[no];
        return;
    }
    int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
    findans(f1,l,mid);
    findans(f2,mid+1,r);
}


void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;
    build(1,0,n-1);
    for(int i = 0; i < k; i++) {
        if(op[i] == 1) attadd(1,0,n-1,left[i],right[i],height[i]);
        if(op[i] == 2) attrem(1,0,n-1,left[i],right[i],height[i]);
    }
    findans(1,0,n-1);
    for(int i = 0; i < n; i++) {
        finalHeight[i] = a[i];
    }
}

Compilation message (stderr)

wall.cpp: In function 'void flush(int, int, int)':
wall.cpp:34:35: warning: unused variable 'mid' [-Wunused-variable]
   34 |             int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
      |                                   ^~~
wall.cpp:53:35: warning: unused variable 'mid' [-Wunused-variable]
   53 |             int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
      |                                   ^~~

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