oj.uz

Submission #535290

# Submission time Handle Problem Language Result Execution time Memory
535290 2022-03-09T23:25:13 Z smth Wall (IOI14_wall) C++14
100 / 100
 845 ms 119272 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int mini[8000002],maxi[8000000], lazymin[8000000],lazymax[8000000],fin[2000002];
bool ispmin[8000003], ispmax[8000003];
void add(int le,int ri,int l,int r,int h, int ind)
{
    if(l<=le && ri<=r)
    {
        lazymax[ind]=max(lazymax[ind],h);ispmax[ind]=1;
    }
    if(ispmin[ind])
    {
            mini[ind]=min(mini[ind],lazymin[ind]);
            maxi[ind]=min(maxi[ind],lazymin[ind]);

         if(le!=ri)
        {
            lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
            lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
            lazymax[2*ind]=min(lazymax[2*ind],lazymin[ind]);
            lazymax[2*ind+1]=min(lazymax[2*ind+1],lazymin[ind]);
            ispmin[2*ind]=ispmin[2*ind+1]=ispmax[2*ind]=ispmax[2*ind+1]=1;
        }
        lazymin[ind]=100000000;ispmin[ind]=0;

    }
    if(ispmax[ind])
    {
        maxi[ind]=max(maxi[ind],lazymax[ind]);
        mini[ind]=max(mini[ind],lazymax[ind]);

        if(le!=ri)
        {
            lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
            lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
            lazymin[2*ind]=max(lazymin[2*ind],lazymax[ind]);
            lazymin[2*ind+1]=max(lazymin[2*ind+1],lazymax[ind]);

            ispmax[2*ind]=ispmax[2*ind+1]=ispmin[2*ind]=ispmin[2*ind+1]=1;
        }
        lazymax[ind]=0;ispmax[ind]=0;
    }
    if(l<=le && ri<=r)return;
    if(l>ri || r<le)return;

    int mid=(le+ri)/2;

    add(le,mid,l,r,h,2*ind);
    add(mid+1,ri,l,r,h,2*ind+1);

    mini[ind]=min(mini[2*ind],mini[2*ind+1]);
    maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);

}

void rem(int le,int ri,int l,int r,int h, int ind)
{
    if(l<=le && ri<=r)
    {
        lazymin[ind]=min(lazymin[ind],h);
        ispmin[ind]=1;
    }
    if(ispmax[ind])
    {
               maxi[ind]=max(maxi[ind],lazymax[ind]);
               mini[ind]=max(mini[ind],lazymax[ind]);


        if(le!=ri)
        {
            lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
            lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
            lazymin[2*ind]=max(lazymin[2*ind],lazymax[ind]);
            lazymin[2*ind+1]=max(lazymin[2*ind+1],lazymax[ind]);

            ispmax[2*ind]=ispmax[2*ind+1]=ispmin[2*ind]=ispmin[2*ind+1]=1;
        }

        lazymax[ind]=0;ispmax[ind]=0;
    }

    if(ispmin[ind])
    {
        mini[ind]=min(mini[ind],lazymin[ind]);
        maxi[ind]=min(maxi[ind],lazymin[ind]);


            if(le!=ri)
        {
            lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
            lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
            lazymax[2*ind]=min(lazymax[2*ind],lazymin[ind]);
            lazymax[2*ind+1]=min(lazymax[2*ind+1],lazymin[ind]);
            ispmin[2*ind]=ispmin[2*ind+1]=ispmax[2*ind]=ispmax[2*ind+1]=1;
        }

        lazymin[ind]=100000000;ispmin[ind]=0;

    }
    if(l<=le && ri<=r)return;
    if(l>ri || r<le)return;

    int mid=(le+ri)/2;

    rem(le,mid,l,r,h,2*ind);
    rem(mid+1,ri,l,r,h,2*ind+1);

    mini[ind]=min(mini[2*ind],mini[2*ind+1]);
    maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);

}

void query2(int le,int ri,int ind)
{
    if(ispmin[ind])
    {
        mini[ind]=min(mini[ind],lazymin[ind]);
        maxi[ind]=min(maxi[ind],lazymin[ind]);


            if(le!=ri)
        {
            lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
            lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
            lazymax[2*ind]=min(lazymax[2*ind],lazymin[ind]);
            lazymax[2*ind+1]=min(lazymax[2*ind+1],lazymin[ind]);
            ispmin[2*ind]=ispmin[2*ind+1]=ispmax[2*ind]=ispmax[2*ind+1]=1;
        }

        lazymin[ind]=100000000;ispmin[ind]=0;

    }
     if(ispmax[ind])
    {
               maxi[ind]=max(maxi[ind],lazymax[ind]);
               mini[ind]=max(mini[ind],lazymax[ind]);


        if(le!=ri)
        {
            lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
            lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
            lazymin[2*ind]=max(lazymin[2*ind],lazymax[ind]);
            lazymin[2*ind+1]=max(lazymin[2*ind+1],lazymax[ind]);

            ispmax[2*ind]=ispmax[2*ind+1]=ispmin[2*ind]=ispmin[2*ind+1]=1;
        }

        lazymax[ind]=0;ispmax[ind]=0;
    }


     if(mini[ind]==maxi[ind])
    {
        for(int i=le;i<=ri;i++)fin[i]=mini[ind];
        return;
    }
    if(le==ri){
      return;
    }

    int mid=(le+ri)/2;
    query2(le,mid,2*ind);
    query2(mid+1,ri,2*ind+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    int i;
    for(i=0;i<8000000;i++)lazymin[i]=100000000;
    for(i=0;i<k;i++)
    {
        left[i]++;
        right[i]++;
        if(op[i]==1)add(1,n,left[i],right[i],height[i],1);
        else rem(1,n,left[i],right[i],height[i],1);
    }

    query2(1,n,1);

    for(i=0;i<n;i++)finalHeight[i]=fin[i+1];

  return;
}

/*
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 15 ms 31700 KB Output is correct
3 Correct 15 ms 31680 KB Output is correct
4 Correct 30 ms 32204 KB Output is correct
5 Correct 20 ms 32208 KB Output is correct
6 Correct 25 ms 32216 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 139 ms 39456 KB Output is correct
3 Correct 286 ms 35888 KB Output is correct
4 Correct 845 ms 53688 KB Output is correct
5 Correct 319 ms 54680 KB Output is correct
6 Correct 307 ms 53080 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 16 ms 31712 KB Output is correct
3 Correct 15 ms 31700 KB Output is correct
4 Correct 21 ms 32212 KB Output is correct
5 Correct 19 ms 32212 KB Output is correct
6 Correct 19 ms 32316 KB Output is correct
7 Correct 15 ms 31588 KB Output is correct
8 Correct 143 ms 39464 KB Output is correct
9 Correct 296 ms 35972 KB Output is correct
10 Correct 828 ms 53680 KB Output is correct
11 Correct 286 ms 54660 KB Output is correct
12 Correct 291 ms 53204 KB Output is correct
13 Correct 13 ms 31572 KB Output is correct
14 Correct 142 ms 45344 KB Output is correct
15 Correct 57 ms 33724 KB Output is correct
16 Correct 778 ms 53948 KB Output is correct
17 Correct 290 ms 53276 KB Output is correct
18 Correct 294 ms 53280 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 15 ms 31724 KB Output is correct
3 Correct 16 ms 31700 KB Output is correct
4 Correct 23 ms 32212 KB Output is correct
5 Correct 18 ms 32320 KB Output is correct
6 Correct 19 ms 32212 KB Output is correct
7 Correct 14 ms 31572 KB Output is correct
8 Correct 138 ms 39416 KB Output is correct
9 Correct 270 ms 35916 KB Output is correct
10 Correct 764 ms 53604 KB Output is correct
11 Correct 288 ms 54688 KB Output is correct
12 Correct 290 ms 53180 KB Output is correct
13 Correct 13 ms 31544 KB Output is correct
14 Correct 137 ms 45192 KB Output is correct
15 Correct 54 ms 33848 KB Output is correct
16 Correct 794 ms 53860 KB Output is correct
17 Correct 292 ms 53324 KB Output is correct
18 Correct 287 ms 53280 KB Output is correct
19 Correct 751 ms 119112 KB Output is correct
20 Correct 723 ms 116636 KB Output is correct
21 Correct 725 ms 119268 KB Output is correct
22 Correct 720 ms 116684 KB Output is correct
23 Correct 726 ms 116608 KB Output is correct
24 Correct 717 ms 116748 KB Output is correct
25 Correct 732 ms 116688 KB Output is correct
26 Correct 743 ms 119272 KB Output is correct
27 Correct 723 ms 119224 KB Output is correct
28 Correct 715 ms 116684 KB Output is correct
29 Correct 725 ms 116648 KB Output is correct
30 Correct 719 ms 116636 KB Output is correct