oj.uz

Submission #927224

# Submission time Handle Problem Language Result Execution time Memory
927224 2024-02-14T12:54:52 Z Nurislam Wall (IOI14_wall) C++14
100 / 100
 818 ms 71508 KB 
//~ #include "wall.h"
#include <bits/stdc++.h>
//~ #include "grader.cpp"

using namespace std;

#define pb push_back
#define ff first
#define ss second
#define ll long long
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
const int N = 2e6+5;

int add[N*4],rem[N*4];
void build(int v,int tl,int tr){
   if(tl==tr){
      add[v]=0;
      rem[v]=1e9;
   }
   else{
      int tm=(tl+tr)/2;
      build(v*2,tl,tm);
      build(v*2+1,tm+1,tr);
   }
}
void push(int v){
   add[v*2]=max(add[v*2],add[v]);
   rem[v*2]=max(rem[v*2],add[v]);
   add[v*2]=min(add[v*2],rem[v]);
   rem[v*2]=min(rem[v*2],rem[v]);
   add[v*2+1]=max(add[v*2+1],add[v]);
   rem[v*2+1]=max(rem[v*2+1],add[v]);
   add[v*2+1]=min(add[v*2+1],rem[v]);
   rem[v*2+1]=min(rem[v*2+1],rem[v]);
   add[v]=0;rem[v]=1e9;
}
void update(int v,int tl,int tr,int l,int r,int x,int type){
   if(r<tl or l>tr)return;
   if(l<=tl && tr<=r){
      if(type==1){
         add[v]=max(add[v],x);
         rem[v]=max(rem[v],x);
      }
      else{
         add[v]=min(add[v],x);
         rem[v]=min(rem[v],x);
      }
      return;
   }
   push(v);
   int tm=(tl+tr)/2;
   update(v*2,tl,tm,l,r,x,type);
   update(v*2+1,tm+1,tr,l,r,x,type);
}
int get(int v,int tl,int tr,int pos){
   if(tl==tr)return add[v];
   push(v);
   int tm=(tl+tr)/2;
   if(pos<=tm)return get(v*2,tl,tm,pos);
   else return get(v*2+1,tm+1,tr,pos);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   build(1,1,n);
   for(int i=0;i<k;i++){
      update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
   }
   for(int i=0;i<n;i++){
      finalHeight[i]=get(1,1,n,i+1);
   }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 99 ms 10320 KB Output is correct
3 Correct 123 ms 8028 KB Output is correct
4 Correct 337 ms 22664 KB Output is correct
5 Correct 226 ms 23768 KB Output is correct
6 Correct 256 ms 22172 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 5 ms 2824 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 104 ms 15944 KB Output is correct
9 Correct 124 ms 11820 KB Output is correct
10 Correct 337 ms 22668 KB Output is correct
11 Correct 231 ms 23728 KB Output is correct
12 Correct 223 ms 22164 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 110 ms 15992 KB Output is correct
15 Correct 21 ms 5724 KB Output is correct
16 Correct 341 ms 22928 KB Output is correct
17 Correct 229 ms 22352 KB Output is correct
18 Correct 236 ms 22352 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 2696 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 108 ms 15948 KB Output is correct
9 Correct 121 ms 11808 KB Output is correct
10 Correct 336 ms 22684 KB Output is correct
11 Correct 227 ms 23636 KB Output is correct
12 Correct 223 ms 22164 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 102 ms 15996 KB Output is correct
15 Correct 21 ms 5776 KB Output is correct
16 Correct 358 ms 22952 KB Output is correct
17 Correct 233 ms 22348 KB Output is correct
18 Correct 230 ms 22352 KB Output is correct
19 Correct 810 ms 71332 KB Output is correct
20 Correct 789 ms 69076 KB Output is correct
21 Correct 776 ms 71316 KB Output is correct
22 Correct 799 ms 68804 KB Output is correct
23 Correct 775 ms 69088 KB Output is correct
24 Correct 774 ms 68916 KB Output is correct
25 Correct 782 ms 69012 KB Output is correct
26 Correct 818 ms 71404 KB Output is correct
27 Correct 810 ms 71508 KB Output is correct
28 Correct 774 ms 69008 KB Output is correct
29 Correct 784 ms 68892 KB Output is correct
30 Correct 777 ms 69104 KB Output is correct