oj.uz

Submission #754703

# Submission time Handle Problem Language Result Execution time Memory
754703 2023-06-08T11:37:42 Z A_D Wall (IOI14_wall) C++17
100 / 100
 1562 ms 162092 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define F first
#define S second
using namespace std;

const int N=2e6+100;

int mx[4*N];
int mx2[4*N];
int mn[4*N];
int mn2[4*N];

void chmn(int p,int s,int e,int h)
{
  if(mn[p]>=h){
    return;
  }
  mn[p]=h;
  if(mx[p]<h){
    mx[p]=h;
    mx2[p]=-1e9;
  }
  else if(mx2[p]<h){
    mx2[p]=h;
  }
}

void chmx(int p,int s,int e,int h)
{
  if(mx[p]<=h){
    return;
  }
  mx[p]=h;
  if(mn[p]>h){
    mn[p]=h;
    mn2[p]=1e9;
  }
  else if(mn2[p]<h){
    mn2[p]=h;
  }
}

void fix(int p,int s,int e)
{
  if(s!=e){
    int mid=(s+e)/2;
    chmn(p*2,s,mid,mn[p]);
    chmn(p*2+1,mid+1,e,mn[p]);

    chmx(p*2,s,mid,mx[p]);
    chmx(p*2+1,mid+1,e,mx[p]);
  }
}
void com(int p,int s,int e)
{
  int a[]={mn[p*2],mn[p*2+1],mn2[p*2],mn2[p*2+1]};
  sort(a,a+4);
  mn[p]=a[0];
  mn2[p]=a[1]!=a[0] ? a[1] : a[2];
  int b[]={mx[p*2],mx[p*2+1],mx2[p*2],mx2[p*2+1]};
  sort(b,b+4);
  mx[p]=b[3];
  mx2[p]=b[2]!=b[3] ? b[2] : b[1];
}


void update(int p,int s,int e,int a,int b,int h,int t)
{
    if(t==1){
      fix(p,s,e);
      if(s>b || e<a || mn[p]>=h){
        return;
      }
      if( a<=s && e<=b && mn2[p]>h ){
        chmn(p,s,e,h);
        return;
      }
      int mid=(s+e)/2;
      update(p*2,s,mid,a,b,h,t);
      update(p*2+1,mid+1,e,a,b,h,t);
      com(p,s,e);
    }
    else{
      fix(p,s,e);
      if(s>b || e<a || mx[p]<=h){
        return;
      }
      if( a<=s && e<=b && mx2[p]<h ){
        chmx(p,s,e,h);
        return;
      }
      int mid=(s+e)/2;
      update(p*2,s,mid,a,b,h,t);
      update(p*2+1,mid+1,e,a,b,h,t);
      com(p,s,e);
    }
}
int get(int p,int s,int e,int i)
{
  fix(p,s,e);
  
  if(s==e){
    return mx[p];
  }
  int mid=(s+e)/2;
  if(i<=mid){
    return get(p*2,s,mid,i);
  }
  else{
    return get(p*2+1,mid+1,e,i);
  }
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=1;i<=4*n;i++){
      mn[i]=mx[i]=0;
      mn2[i]=1e9;
      mx2[i]=-1e9;
    }
    for(int i=0;i<k;i++){
      update(1,0,n-1,left[i],right[i],height[i],op[i]);
    }
    for(int i=0;i<n;i++){
      finalHeight[i]=get(1,0,n-1,i);
    }
    //cout<<"\n";
}

// https://oj.uz/problem/submit/IOI14_wall

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 452 KB Output is correct
3 Correct 3 ms 324 KB Output is correct
4 Correct 11 ms 1152 KB Output is correct
5 Correct 9 ms 1108 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 126 ms 8620 KB Output is correct
3 Correct 78 ms 5460 KB Output is correct
4 Correct 209 ms 23108 KB Output is correct
5 Correct 218 ms 23292 KB Output is correct
6 Correct 319 ms 24012 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 320 KB Output is correct
4 Correct 10 ms 1156 KB Output is correct
5 Correct 9 ms 1220 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 131 ms 14028 KB Output is correct
9 Correct 75 ms 8652 KB Output is correct
10 Correct 189 ms 24540 KB Output is correct
11 Correct 224 ms 25700 KB Output is correct
12 Correct 303 ms 24140 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 131 ms 13932 KB Output is correct
15 Correct 54 ms 2484 KB Output is correct
16 Correct 1029 ms 24896 KB Output is correct
17 Correct 529 ms 24268 KB Output is correct
18 Correct 556 ms 24340 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 328 KB Output is correct
4 Correct 10 ms 1148 KB Output is correct
5 Correct 9 ms 1108 KB Output is correct
6 Correct 9 ms 1108 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 124 ms 13900 KB Output is correct
9 Correct 75 ms 8576 KB Output is correct
10 Correct 198 ms 24512 KB Output is correct
11 Correct 230 ms 25564 KB Output is correct
12 Correct 322 ms 24024 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 133 ms 13860 KB Output is correct
15 Correct 57 ms 2520 KB Output is correct
16 Correct 997 ms 24972 KB Output is correct
17 Correct 534 ms 24164 KB Output is correct
18 Correct 539 ms 24212 KB Output is correct
19 Correct 1530 ms 161928 KB Output is correct
20 Correct 1562 ms 159432 KB Output is correct
21 Correct 1490 ms 162092 KB Output is correct
22 Correct 1496 ms 159424 KB Output is correct
23 Correct 1504 ms 159428 KB Output is correct
24 Correct 1504 ms 159572 KB Output is correct
25 Correct 1492 ms 159464 KB Output is correct
26 Correct 1491 ms 161856 KB Output is correct
27 Correct 1496 ms 161900 KB Output is correct
28 Correct 1525 ms 159304 KB Output is correct
29 Correct 1509 ms 159408 KB Output is correct
30 Correct 1535 ms 159324 KB Output is correct