oj.uz

Submission #535282

# Submission time Handle Problem Language Result Execution time Memory
535282 2022-03-09T22:07:47 Z daisy Wall (IOI14_wall) C++17
0 / 100
 141 ms 12116 KB 
#include<iostream>
#include<cstring>
#include<algorithm>
#include "wall.h"
using namespace std;
int a[1000005],y[1000005],tree[4000005],mi[4000005],ma[4000005],st[1000005],re[1000005];
int lazy1[4000005],lazy2[4000005];
bool b[1000005];
void update(int node,int l,int r,int le,int ri,int type,int h)
{
    if(le<=y[l] && y[r]<=ri)
    {
        if(type==1)
            lazy1[node]=max(lazy1[node],h);

        else lazy2[node]=min(lazy2[node],h);
    }
        if(l!=r)
        {
            lazy1[2*node]=max(lazy1[2*node],lazy1[node]);
            lazy1[2*node+1]=max(lazy1[2*node+1],lazy1[node]);

            lazy2[2*node]=min(lazy2[2*node],lazy2[node]);
            lazy2[2*node+1]=min(lazy2[2*node+1],lazy2[node]);
        }


    if((le<=y[l] && y[r]<=ri) || y[l]>ri || y[r]<le) return;

    int mid=(l+r)/2;

    update(2*node,l,mid,le,ri,type,h);
    update(2*node+1,mid+1,r,le,ri,type,h);
}
void updatefinal(int node,int l,int r)
{
        if(l!=r)
        {
            lazy1[2*node]=max(lazy1[2*node],lazy1[node]);
            lazy1[2*node+1]=max(lazy1[2*node+1],lazy1[node]);

            lazy2[2*node]=min(lazy2[2*node],lazy2[node]);
            lazy2[2*node+1]=min(lazy2[2*node+1],lazy2[node]);


            lazy1[2*node]=min(lazy1[2*node],lazy2[node]);
            lazy2[2*node]=max(lazy2[2*node],lazy1[node]);

            lazy1[2*node+1]=min(lazy1[2*node+1],lazy2[node]);
            lazy2[2*node+1]=max(lazy2[2*node+1],lazy1[node]);
            lazy1[node]=-1;
            lazy2[node]=1000000;
        }

    if(l==r) {re[y[l]]=lazy1[node];return;}

    int mid=(l+r)/2;

    updatefinal(2*node,l,mid);
    updatefinal(2*node+1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0;i<k;i++)
    {
        a[2*i]=left[i];
        a[2*i+1]=right[i];
    }
    sort(a,a+2*k);
    y[1]=a[0];
    int in=2;
    for(int i=1;i<2*k;i++)
    {
        if(a[i]!=a[i-1])
        {y[in]=a[i];in++;}
    }
    in--;
    for(int i=1;i<=in;i++) {lazy2[i]=1000000;lazy1[i]=-1;}
    for(int i=0;i<k;i++)
    {
        if(op[i]==1)  //adding
        {
            update(1,1,in,left[i],right[i],1,height[i]);
        }
        else  //removing
        {
            update(1,1,in,left[i],right[i],2,height[i]);
        }
    }
    updatefinal(1,1,in);
    int p=0,z=1;
    for(int i=0;i<n;i++)
    {
        if(y[z]==i) {p=i;z++;}
        finalHeight[i]=re[p];

    }
    return;
}
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 141 ms 12116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 2 ms 420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 2 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -