oj.uz

Submission #922721

# Submission time Handle Problem Language Result Execution time Memory
922721 2024-02-06T04:12:08 Z Aiperiii Wall (IOI14_wall) C++14
100 / 100
 870 ms 71680 KB 
#include <bits/stdc++.h>
#include "wall.h"
//#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
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;
}

/*signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   int n,q;
   cin>>n>>q;
   int type[q],l[q],r[q],h[q],res[q];
   for(int i=0;i<q;i++){
      cin>>type[i]>>l[i]>>r[i]>>h[i];
   }
   buildWall(n,q,type,l,r,h,res);
   for(int i=0;i<n;i++)cout<<res[i]<<' ';
}*/
/*
 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2500 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 5 ms 2836 KB Output is correct
5 Correct 5 ms 2648 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 104 ms 16276 KB Output is correct
3 Correct 119 ms 8784 KB Output is correct
4 Correct 351 ms 22556 KB Output is correct
5 Correct 241 ms 23596 KB Output is correct
6 Correct 235 ms 22164 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 2652 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 2392 KB Output is correct
8 Correct 104 ms 16028 KB Output is correct
9 Correct 121 ms 11808 KB Output is correct
10 Correct 355 ms 22624 KB Output is correct
11 Correct 240 ms 23724 KB Output is correct
12 Correct 240 ms 22176 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 108 ms 15956 KB Output is correct
15 Correct 24 ms 5724 KB Output is correct
16 Correct 357 ms 23056 KB Output is correct
17 Correct 230 ms 22344 KB Output is correct
18 Correct 230 ms 22356 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2504 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 5 ms 2760 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 5 ms 2824 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 100 ms 16036 KB Output is correct
9 Correct 126 ms 11808 KB Output is correct
10 Correct 341 ms 22600 KB Output is correct
11 Correct 224 ms 23732 KB Output is correct
12 Correct 223 ms 22352 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 103 ms 15924 KB Output is correct
15 Correct 23 ms 5724 KB Output is correct
16 Correct 349 ms 22928 KB Output is correct
17 Correct 225 ms 22356 KB Output is correct
18 Correct 234 ms 22352 KB Output is correct
19 Correct 814 ms 71344 KB Output is correct
20 Correct 790 ms 68940 KB Output is correct
21 Correct 810 ms 71372 KB Output is correct
22 Correct 792 ms 68852 KB Output is correct
23 Correct 813 ms 68980 KB Output is correct
24 Correct 794 ms 68940 KB Output is correct
25 Correct 834 ms 68896 KB Output is correct
26 Correct 822 ms 71372 KB Output is correct
27 Correct 839 ms 71680 KB Output is correct
28 Correct 828 ms 68936 KB Output is correct
29 Correct 870 ms 68912 KB Output is correct
30 Correct 811 ms 69024 KB Output is correct