Submission #227748

#	Time	Username	Problem	Language	Result	Execution time	Memory
227748		2fat2code	Wall (IOI14_wall)	C++17	100 / 100	718 ms	77432 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 u[4*nmax],d[4*nmax],ans[nmax],lazy[4*nmax];

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

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){
            u[nod]=max(u[nod],h);
            d[nod]=max(d[nod],h);
        }
        else{
            u[nod]=min(u[nod],h);
            d[nod]=min(d[nod],h);
        }
    }
    else{
        lazi(2*nod,u[nod],d[nod]);
        lazi(2*nod+1,u[nod],d[nod]);
        u[nod]=0;
        d[nod]=1e18;
        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);
    }
}

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

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   // for(int i=1;i<=4*n;i++) d[i]=1e18;
    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:46:16: warning: overflow in implicit constant conversion [-Woverflow]
         d[nod]=1e18;
                ^~~~

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