oj.uz

Submission #751526

# Submission time Handle Problem Language Result Execution time Memory
751526 2023-05-31T16:54:53 Z amin Wall (IOI14_wall) C++14
61 / 100
 606 ms 58432 KB 
#include "wall.h"
 #include <bits/stdc++.h>
using namespace std;
 #define ll long long

int ma[4000000];
int mi[4000000];
int a[4000003];
int z;
int b[4000003];
int ans=0;
int n;


void push(int v)
{
//cout<<v<<endl;
   if(ma[v]<ma[v*2]&&ma[v]<mi[v*2])
   {
    //   cout<<v<<endl;

       ma[v*2]=mi[v*2]=ma[v];

   }else
   if(mi[v]>mi[v*2]&&mi[v]>ma[v*2])
   {
    mi[v*2]=ma[v*2]=mi[v];
   // cout<<v<<endl;
   }
 else
 {
   mi[v*2]=max(mi[v*2],mi[v]);
   ma[v*2]=min(ma[v*2],ma[v]);
 }
  if(ma[v]<ma[v*2+1]&&ma[v]<mi[v*2+1])
   {
      // cout<<v<<endl;
       ma[v*2+1]=mi[v*2+1]=ma[v];
   }else
   if(mi[v]>mi[v*2+1]&&mi[v]>ma[v*2+1])
   {
      // cout<<v<<endl;
    mi[v*2+1]=ma[v*2+1]=mi[v];
   }
 else
 {
   mi[v*2+1]=max(mi[v*2+1],mi[v]);
   ma[v*2+1]=min(ma[v*2+1],ma[v]);
 }
mi[v]=0;
ma[v]=1e9;
}
void update(int v,int tl,int tr,int l,int r,int t,int val)
{
  //  cout<<tl<<' '<<tr<<endl;
    if(l>r)
        return ;

    if(tl==l&&tr==r)
    {
     //   cout<<tl<<' '<<tr<<endl;
     if(t==1)
     {
         mi[v]=max(mi[v],val);
         ma[v]=max(mi[v],ma[v]);
     }else
     {
         ma[v]=min(ma[v],val);
         mi[v]=min(mi[v],ma[v]);
     }
    /* if(tl==3&&tr==5)
     {
       //  cout<<mi[v]<<' '<<ma[v]<<endl;
     }*/
        return ;

    }
   // cout<<tl<<' '<<tr<<endl;
    push(v);
    int tm=(tl+tr)>>1;
   update(v*2,tl,tm,l,min(r,tm),t,val);
   update(v*2+1,tm+1,tr,max(tm+1,l),r,t,val);
  //  merg(v,v*2,v*2+1);

}
int get(int v,int tl,int tr,int pos)
{
    if(tl>pos||pos>tr)
        return 1000000001;
    if(tl==tr)
    {
      //  cout<<ma[v]<<endl;
        return mi[v];
       // cout<<ma[v]<<endl;
    }
    push(v);
    int tm=(tl+tr)/2;
    return min(get(v*2,tl,tm,pos),get(v*2+1,tm+1,tr,pos));

}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{

for(int i=0;i<=4*n;i++)
{
    ma[i]=1000000000;
}
for(int i=0;i<k;i++)
{
update(1,0,n-1,left[i],right[i],op[i],height[i]);
}

for(int i=0;i<n;i++)
{
    finalHeight[i]=get(1,0,n-1,i);
}
return ;











}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 9 ms 852 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 148 ms 13872 KB Output is correct
3 Correct 173 ms 7916 KB Output is correct
4 Correct 486 ms 20916 KB Output is correct
5 Correct 281 ms 21916 KB Output is correct
6 Correct 301 ms 20332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 6 ms 772 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 161 ms 13972 KB Output is correct
9 Correct 175 ms 7944 KB Output is correct
10 Correct 472 ms 20896 KB Output is correct
11 Correct 289 ms 21896 KB Output is correct
12 Correct 303 ms 20308 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 165 ms 13904 KB Output is correct
15 Correct 34 ms 2016 KB Output is correct
16 Correct 606 ms 21192 KB Output is correct
17 Correct 273 ms 20556 KB Output is correct
18 Correct 267 ms 20564 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 832 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 140 ms 13912 KB Output is correct
9 Correct 167 ms 8016 KB Output is correct
10 Correct 494 ms 20880 KB Output is correct
11 Correct 278 ms 21880 KB Output is correct
12 Correct 268 ms 20352 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 136 ms 13900 KB Output is correct
15 Correct 32 ms 1912 KB Output is correct
16 Correct 573 ms 21148 KB Output is correct
17 Correct 268 ms 20604 KB Output is correct
18 Correct 269 ms 20572 KB Output is correct
19 Runtime error 191 ms 58432 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -