oj.uz

Submission #1089195

# Submission time Handle Problem Language Result Execution time Memory
1089195 2024-09-16T07:16:09 Z LucasLe Wall (IOI14_wall) C++17
100 / 100
 1786 ms 44624 KB 
#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>
 
#define                pii  pair<int, int>
#define                 fi  first
#define                 se  second
#define                 ld  long double
#define                 vi  vector<int>
#define                vii  vector<vector<int>>
#define             all(v)  (v).begin(), (v).end()
#define       rep(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define       per(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
 
using namespace std;
 
const int MOD = 1e9 + 7;
 
int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}
 
int mul(int a, int b) {
  (a *= b) %= MOD;
  return a;
}
 
int ceil(int x, int y) {
  return (x + y - 1) / y;
}
 
int bin_pow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = res * x % MOD;
    x = x * x % MOD;
    y >>= 1;
  }
  return res;
}
 
template<class T> bool minimize(T& a, T b) {
  if (a > b) return a = b, true;
  return false;
}
 
template<class T> bool maximize(T& a, T b) {
  if (a < b) return a = b, true;
  return false;
}
 
const int maxn = 2e6 + 5;
const int SIZE = 1415;
 
int n, q;
int a[maxn + 5];
int left_bound[SIZE + 5], right_bound[SIZE + 5];
int moonx[SIZE + 5], moony[SIZE + 5];
 
void updatefull(int t, int x, int h) {
  if (t == 1) {
    moony[x] = max(moony[x], h);
    moonx[x] = max(moonx[x], h);
  } else {
    moonx[x] = min(moonx[x], h);
    moony[x] = min(moony[x], h);
  }
}
 
void updatemanual(int t, int x, int l, int r, int h) {
  for (int i = left_bound[x]; i <= right_bound[x]; ++i) {
    a[i] = min(a[i], moonx[x]);
    a[i] = max(a[i], moony[x]);
  }
  for (int i = l; i <= r; ++i) {
    if (t == 1) {
      a[i] = max(a[i], h);
    } else {
      a[i] = min(a[i], h);
    }
  }
  moonx[x] = (moony[x] = a[left_bound[x]]);
  for (int i = left_bound[x]; i <= right_bound[x]; ++i) {
    moonx[x] = max(a[i], moonx[x]);
    moony[x] = min(a[i], moony[x]);
  }
}
 
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
  n = N, q = K;
  for (int i = 1; i <= n; ++i) {
    int x = ceil(i, SIZE);
    left_bound[x] = n + 1;
  }
  for (int i = 1; i <= n; ++i) {
    int x = ceil(i, SIZE);
    left_bound[x] = min(left_bound[x], i);
    right_bound[x] = i;
  }
  for (int _ = 0; _ < q; ++_) {
    int t, l, r, h;
    t = op[_];
    l = left[_] + 1;
    r = right[_] + 1;
    h = height[_];
    int block_l = ceil(l, SIZE);
    int block_r = ceil(r, SIZE);
    for (int i = block_l + 1; i <= block_r - 1; ++i)
      updatefull(t, i, h);
    if (block_l == block_r) { 
      updatemanual(t, block_l, l, r, h);
    } else {
      updatemanual(t, block_l, l, right_bound[block_l], h);
      updatemanual(t, block_r, left_bound[block_r], r, h);
    }
  }
  for (int i = 1; i <= n; ++i) {
    int x = ceil(i, SIZE);
    if (moonx[x] != -1 && a[i] > moonx[x]) a[i] = moonx[x];
    if (moony[x] != -1 && a[i] < moony[x]) a[i] = moony[x];
    finalHeight[i - 1] = a[i];
  }
}

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 348 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 14 ms 604 KB Output is correct
5 Correct 12 ms 600 KB Output is correct
6 Correct 13 ms 604 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 96 ms 11228 KB Output is correct
3 Correct 573 ms 5888 KB Output is correct
4 Correct 1515 ms 14312 KB Output is correct
5 Correct 796 ms 14972 KB Output is correct
6 Correct 773 ms 14416 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 576 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 14 ms 692 KB Output is correct
5 Correct 13 ms 604 KB Output is correct
6 Correct 12 ms 680 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 92 ms 11168 KB Output is correct
9 Correct 570 ms 5932 KB Output is correct
10 Correct 1478 ms 14316 KB Output is correct
11 Correct 804 ms 15132 KB Output is correct
12 Correct 769 ms 14312 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 92 ms 11340 KB Output is correct
15 Correct 86 ms 1616 KB Output is correct
16 Correct 1485 ms 14412 KB Output is correct
17 Correct 763 ms 14184 KB Output is correct
18 Correct 769 ms 14164 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 604 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 15 ms 696 KB Output is correct
5 Correct 12 ms 604 KB Output is correct
6 Correct 12 ms 604 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 95 ms 11680 KB Output is correct
9 Correct 581 ms 5812 KB Output is correct
10 Correct 1474 ms 14352 KB Output is correct
11 Correct 788 ms 17644 KB Output is correct
12 Correct 766 ms 16468 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 93 ms 12852 KB Output is correct
15 Correct 87 ms 1616 KB Output is correct
16 Correct 1501 ms 17132 KB Output is correct
17 Correct 782 ms 16464 KB Output is correct
18 Correct 819 ms 16576 KB Output is correct
19 Correct 1683 ms 42320 KB Output is correct
20 Correct 1694 ms 37968 KB Output is correct
21 Correct 1717 ms 43664 KB Output is correct
22 Correct 1668 ms 39176 KB Output is correct
23 Correct 1772 ms 39152 KB Output is correct
24 Correct 1706 ms 40088 KB Output is correct
25 Correct 1697 ms 40196 KB Output is correct
26 Correct 1786 ms 44624 KB Output is correct
27 Correct 1718 ms 44540 KB Output is correct
28 Correct 1675 ms 39980 KB Output is correct
29 Correct 1693 ms 40160 KB Output is correct
30 Correct 1756 ms 40108 KB Output is correct