oj.uz

Submission #610976

# Submission time Handle Problem Language Result Execution time Memory
610976 2022-07-28T20:57:06 Z APROHACK Wall (IOI14_wall) C++14
100 / 100
 1283 ms 240340 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int N, K, blocksz;
vector<int>ans, ans2;
vector<int>values;
struct segTree
{
  int dd, ht, minimum, maximum, mid;
  segTree *L, *R;
  segTree(int l, int r){
    dd = l, ht = r;
    mid = (l+r)/2;
    minimum = 0, maximum = 1000000000;
    if(l!=r){
      L=new segTree(l, mid);
      R=new segTree(mid+1, r);
    }
  }
  void lazy(){
    L->operate(dd, mid, 1, minimum);
    L->operate(dd, mid, 2, maximum);
    R->operate(mid+1, ht, 1, minimum);
    R->operate(mid+1, ht, 2, maximum);
    minimum = 0;
    maximum = 1000000000;
  }
  void operate(int l, int r, int op, int val){
    if(l == dd && r == ht){
      if(op==1){
        if(minimum < val){
          minimum = val;
          if(maximum < minimum)maximum = minimum;
        }
      }else{
        if(maximum > val){
          maximum = val;
          if(minimum > maximum)minimum = maximum;
        }
      }
    }else{
      lazy();
      if(r<= mid){
        L->operate(l, r, op, val);
      }else if(l > mid){
        R->operate(l, r, op, val);
      }else{
        L->operate(l, mid, op, val);
        R->operate(mid+1, r, op, val);
      }
    }
  }
  void answ(){
    if(dd!=ht){
      lazy();
      L->answ();
      R->answ();
    }else{
      ans.pb(minimum);
    }
  }

};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N=n, K=k;
  for(int i = 0 ; i < n ; i ++){
    values.pb(0);
  }
  segTree *st = new segTree(0, n-1);
  for(int  i = 0 ; i < k ; ++i){
    st->operate(left[i], right[i], op[i], height[i]);
  }
  st->answ();
  for(int i = 0 ; i < n ; i ++)finalHeight[i] = ans[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 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 13 ms 1500 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 8 ms 1492 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 132 ms 8016 KB Output is correct
3 Correct 302 ms 5520 KB Output is correct
4 Correct 906 ms 18964 KB Output is correct
5 Correct 433 ms 19428 KB Output is correct
6 Correct 405 ms 19448 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 352 KB Output is correct
4 Correct 10 ms 1556 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Correct 8 ms 1524 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 130 ms 8128 KB Output is correct
9 Correct 289 ms 5520 KB Output is correct
10 Correct 916 ms 19012 KB Output is correct
11 Correct 432 ms 19512 KB Output is correct
12 Correct 404 ms 19504 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 143 ms 8072 KB Output is correct
15 Correct 53 ms 2696 KB Output is correct
16 Correct 986 ms 19196 KB Output is correct
17 Correct 425 ms 19204 KB Output is correct
18 Correct 433 ms 19200 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 1528 KB Output is correct
5 Correct 7 ms 1528 KB Output is correct
6 Correct 7 ms 1524 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 130 ms 8080 KB Output is correct
9 Correct 298 ms 5628 KB Output is correct
10 Correct 845 ms 18952 KB Output is correct
11 Correct 401 ms 19456 KB Output is correct
12 Correct 429 ms 19396 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 137 ms 8024 KB Output is correct
15 Correct 49 ms 2740 KB Output is correct
16 Correct 989 ms 19200 KB Output is correct
17 Correct 490 ms 19236 KB Output is correct
18 Correct 432 ms 19204 KB Output is correct
19 Correct 1227 ms 229864 KB Output is correct
20 Correct 1214 ms 237800 KB Output is correct
21 Correct 1238 ms 240228 KB Output is correct
22 Correct 1215 ms 237852 KB Output is correct
23 Correct 1246 ms 237944 KB Output is correct
24 Correct 1224 ms 237772 KB Output is correct
25 Correct 1199 ms 237736 KB Output is correct
26 Correct 1261 ms 240340 KB Output is correct
27 Correct 1213 ms 240296 KB Output is correct
28 Correct 1281 ms 237804 KB Output is correct
29 Correct 1252 ms 237732 KB Output is correct
30 Correct 1283 ms 237788 KB Output is correct