oj.uz

Submission #1023500

# Submission time Handle Problem Language Result Execution time Memory
1023500 2024-07-14T21:25:16 Z HappyCapybara Wall (IOI14_wall) C++17
100 / 100
 671 ms 99476 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;

int N;
vector<pair<int,int>> lazy;

void merge(int node, pair<int,int> p){
  if (p.second >= lazy[node].first && lazy[node].second >= p.first){
    lazy[node].first = max(lazy[node].first, p.first);
    lazy[node].second = min(lazy[node].second, p.second);
    return;
  }
  if (p.first > lazy[node].second) lazy[node] = {p.first, p.first};
  else lazy[node] = {p.second, p.second};
  return;
}

void prop(int node){
  merge(node*2, lazy[node]);
  merge(node*2+1, lazy[node]);
  lazy[node] = {0, 100000};
  return;
}

void update(int l, int r, pair<int,int> p, int node=1, int tl=0, int tr=N-1){
  if (l <= tl && tr <= r){
    merge(node, p);
    return;
  }
  prop(node);
  int tm = (tl+tr)/2;
  if (l <= tm) update(l, r, p, node*2, tl, tm);
  if (tm+1 <= r) update(l, r, p, node*2+1, tm+1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N = n;
  lazy.resize(4*n, {0, 100000});
  for (int i=0; i<k; i++){
    if (op[i] == 1) update(left[i], right[i], {height[i], 100000});
    else update(left[i], right[i], {0, height[i]});
  }
  for (int i=0; i<n; i++){
    finalHeight[i] = 0;
    int cur = 1, tl = 0, tr = n-1;
    while (tl != tr){
        int tm = (tl+tr)/2;
        if (i <= tm){
            cur = cur*2;
            tr = tm;
        }
        else {
            cur = cur*2+1;
            tl = tm+1;
        }
    }
    while (cur){
      if (finalHeight[i] < lazy[cur].first) finalHeight[i] = lazy[cur].first;
      if (finalHeight[i] > lazy[cur].second) finalHeight[i] = lazy[cur].second;
      cur >>= 1;
    }
  }
  return;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 85 ms 13936 KB Output is correct
3 Correct 115 ms 8020 KB Output is correct
4 Correct 299 ms 21580 KB Output is correct
5 Correct 189 ms 22600 KB Output is correct
6 Correct 187 ms 21008 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 5 ms 964 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 13908 KB Output is correct
9 Correct 109 ms 8100 KB Output is correct
10 Correct 309 ms 21484 KB Output is correct
11 Correct 240 ms 22436 KB Output is correct
12 Correct 193 ms 20848 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 87 ms 13988 KB Output is correct
15 Correct 23 ms 2128 KB Output is correct
16 Correct 402 ms 21844 KB Output is correct
17 Correct 194 ms 21076 KB Output is correct
18 Correct 185 ms 21072 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 7 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 84 ms 13916 KB Output is correct
9 Correct 107 ms 8064 KB Output is correct
10 Correct 308 ms 21588 KB Output is correct
11 Correct 189 ms 22608 KB Output is correct
12 Correct 180 ms 20852 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 88 ms 14008 KB Output is correct
15 Correct 25 ms 2128 KB Output is correct
16 Correct 397 ms 21840 KB Output is correct
17 Correct 200 ms 21048 KB Output is correct
18 Correct 196 ms 21068 KB Output is correct
19 Correct 554 ms 99348 KB Output is correct
20 Correct 591 ms 96712 KB Output is correct
21 Correct 560 ms 99408 KB Output is correct
22 Correct 579 ms 96960 KB Output is correct
23 Correct 574 ms 96764 KB Output is correct
24 Correct 585 ms 96848 KB Output is correct
25 Correct 574 ms 96852 KB Output is correct
26 Correct 602 ms 99256 KB Output is correct
27 Correct 671 ms 99476 KB Output is correct
28 Correct 573 ms 96848 KB Output is correct
29 Correct 577 ms 96852 KB Output is correct
30 Correct 640 ms 96848 KB Output is correct