Submission #1161624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161624		I_FloPPed21	Wall (IOI14_wall)	C++20	100 / 100	670 ms	151576 KiB

wall

#include <iostream>
#include "wall.h"
using namespace std;
const int N=2e6+5;
struct seg
{
    long long val_min,val_max;
} aint[4*N];
void aplica(int nod,seg x)
{
    aint[nod].val_min=max(aint[nod].val_min,x.val_min);
    aint[nod].val_max=max(aint[nod].val_max,aint[nod].val_min);
    aint[nod].val_max=min(aint[nod].val_max,x.val_max);
    aint[nod].val_min=min(aint[nod].val_min,aint[nod].val_max);
}
void propaga(int nod)
{
    aplica(nod*2,aint[nod]);
    aplica(nod*2+1,aint[nod]);
    aint[nod].val_min=0;
    aint[nod].val_max=3e9+2;
}
void update(int nod,int st,int dr,int l,int r,seg x)
{
    if(l<=st&&dr<=r)
    {
        aplica(nod,x);
    }
    else if(l>dr||st>r)
        return ;
    else
    {
        int mij=(st+dr)/2;
        propaga(nod);
        update(nod*2,st,mij,l,r,x);
        update(nod*2+1,mij+1,dr,l,r,x);
    }
}
seg query(int nod,int st,int dr,int poz)
{
    if(st==dr)
        return aint[nod];
    else
    {
        propaga(nod);
        int mij=(st+dr)/2;
        if(poz<=mij)
            return query(nod*2,st,mij,poz);
        else
            return query(nod*2+1,mij+1,dr,poz);
    }
}
const int inf=3e9+2;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=1;i<=4*n;i++)
    {
        aint[i].val_min=0;
        aint[i].val_max=inf;
    }
    for(int i=0; i<k; i++)
    {
        left[i]++;
        right[i]++;
        if(op[i]==1)
        {
            update(1,1,n,left[i],right[i], {height[i],inf});
        }
        else
            update(1,1,n,left[i],right[i], {0,height[i]});
    }

    for(int i=0; i<n; i++)
    {
        finalHeight[i]=query(1,1,n,i+1).val_min;
    }
    return;
}

Compilation message (stderr)

wall.cpp:53:18: warning: overflow in conversion from 'double' to 'int' changes value from '3.000000002e+9' to '2147483647' [-Woverflow]
   53 | const int inf=3e9+2;
      |               ~~~^~

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