oj.uz

Submission #990087

# Submission time Handle Problem Language Result Execution time Memory
990087 2024-05-29T14:04:34 Z huutuan Wall (IOI14_wall) C++14
100 / 100
 377 ms 99568 KB 
#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

const int inf=1e9;

struct SegmentTree{
   int n;
   vector<pair<int, int>> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, {-inf, inf});
   }
   void build(int k, int l, int r){
      if (l==r){
         t[k]={0, 0};
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid);
      build(k<<1|1, mid+1, r);
   }
   void apply(int k, pair<int, int> val){
      if (t[k].second<val.first) t[k]={val.first, val.first};
      else if (t[k].first>val.second) t[k]={val.second, val.second};
      else t[k]={max(t[k].first, val.first), min(t[k].second, val.second)};
   }
   void push(int k){
      if (t[k]!=pair<int, int>{-inf, inf}){
         apply(k<<1, t[k]);
         apply(k<<1|1, t[k]);
         t[k]={-inf, inf};
      }
   }
   void update(int k, int l, int r, int L, int R, pair<int, int> val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
   }
   void get_all(int k, int l, int r, int ans[]){
      if (l==r){
         ans[l]=t[k].first;
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      get_all(k<<1, l, mid, ans);
      get_all(k<<1|1, mid+1, r, ans);
   }
} st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   st.init(n);
   st.build(1, 0, n-1);
   for (int i=0; i<k; ++i){
      int l=left[i], r=right[i], h=height[i];
      int lg=__lg(r-l+1);
      if (op[i]==1){
         st.update(1, 0, n-1, l, r, {h, inf});
      }else{
         st.update(1, 0, n-1, l, r, {-inf, h});
      }
   }
   st.get_all(1, 0, n-1, finalHeight);
   return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:65:11: warning: unused variable 'lg' [-Wunused-variable]
   65 |       int lg=__lg(r-l+1);
      |           ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 888 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 81 ms 13860 KB Output is correct
3 Correct 101 ms 6740 KB Output is correct
4 Correct 284 ms 21456 KB Output is correct
5 Correct 151 ms 22608 KB Output is correct
6 Correct 142 ms 20992 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 3 ms 892 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 14016 KB Output is correct
9 Correct 100 ms 8096 KB Output is correct
10 Correct 282 ms 21588 KB Output is correct
11 Correct 163 ms 22588 KB Output is correct
12 Correct 141 ms 20820 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 83 ms 13980 KB Output is correct
15 Correct 21 ms 2136 KB Output is correct
16 Correct 377 ms 21632 KB Output is correct
17 Correct 156 ms 21076 KB Output is correct
18 Correct 155 ms 21172 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 956 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 4 ms 968 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 13896 KB Output is correct
9 Correct 116 ms 8060 KB Output is correct
10 Correct 288 ms 21508 KB Output is correct
11 Correct 150 ms 22404 KB Output is correct
12 Correct 153 ms 20816 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 94 ms 13932 KB Output is correct
15 Correct 21 ms 2140 KB Output is correct
16 Correct 368 ms 21844 KB Output is correct
17 Correct 155 ms 21108 KB Output is correct
18 Correct 151 ms 21072 KB Output is correct
19 Correct 348 ms 99420 KB Output is correct
20 Correct 339 ms 96848 KB Output is correct
21 Correct 347 ms 99392 KB Output is correct
22 Correct 351 ms 96848 KB Output is correct
23 Correct 344 ms 96852 KB Output is correct
24 Correct 332 ms 96848 KB Output is correct
25 Correct 349 ms 96848 KB Output is correct
26 Correct 349 ms 99568 KB Output is correct
27 Correct 363 ms 99408 KB Output is correct
28 Correct 348 ms 96744 KB Output is correct
29 Correct 343 ms 96792 KB Output is correct
30 Correct 343 ms 96836 KB Output is correct