Submission #227787

#	Time	Username	Problem	Language	Result	Execution time	Memory
227787		2fat2code	Wall (IOI14_wall)	C++17	100 / 100	901 ms	67728 KiB

wall

#include "wall.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int nmax=2000005;

int up[4*nmax],down[4*nmax],ans[nmax],lazy[4*nmax];

void lazi(int nod,int up1,int down1){
    down[nod]=max(down[nod],down1);
    down[nod]=min(down[nod],up1);
    up[nod]=min(up[nod],up1);
    up[nod]=max(up[nod],down1);
}

void update(int l,int r,int le,int ri,int op,int h,int nod){
    if(l>ri || r<le) return;
    else if(l>=le && r<=ri){
        if(op==1){
            up[nod]=max(up[nod],h);
            down[nod]=max(down[nod],h);
        }
        else{
            up[nod]=min(up[nod],h);
            down[nod]=min(down[nod],h);
        }
    }
    else{
        lazi(2*nod,up[nod],down[nod]);
        lazi(2*nod+1,up[nod],down[nod]);
        int mid=l+(r-l)/2;
        update(l,mid,le,ri,op,h,2*nod);
        update(mid+1,r,le,ri,op,h,2*nod+1);
        down[nod]=0;
        up[nod]=1e18;
    }
}

void complete(int l,int r,int nod){
    if(l!=r){
        int mid=l+(r-l)/2;
        lazi(2*nod,up[nod],down[nod]);
        lazi(2*nod+1,up[nod],down[nod]);
        complete(l,mid,2*nod);
        complete(mid+1,r,2*nod+1);
    }
    else{
        ans[l]=up[nod];
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=1;i<=k;i++){
        update(1,n,left[i-1]+1,right[i-1]+1,op[i-1],height[i-1],1);
    }
    complete(1,n,1);
    for(int i=1;i<=n;i++) finalHeight[i-1]=ans[i];
}

Compilation message (stderr)

wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:49:17: warning: overflow in implicit constant conversion [-Woverflow]
         up[nod]=1e18;
                 ^~~~

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