oj.uz

Submission #1089189

# Submission time Handle Problem Language Result Execution time Memory
1089189 2024-09-16T07:09:00 Z LucasLe Wall (IOI14_wall) C++17
61 / 100
 3000 ms 25904 KB 
#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 INF = 1e17;
const int maxn = 2e6 + 5;
const int SIZE = 317;

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];
  }
}

Compilation message

wall.cpp:52:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   52 | const int INF = 1e17;
      |                 ^~~~

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 460 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 13 ms 600 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 7 ms 600 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 88 ms 13908 KB Output is correct
3 Correct 286 ms 7500 KB Output is correct
4 Correct 772 ms 18768 KB Output is correct
5 Correct 352 ms 19796 KB Output is correct
6 Correct 350 ms 18284 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 584 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 648 KB Output is correct
5 Correct 7 ms 672 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 102 ms 13916 KB Output is correct
9 Correct 298 ms 7504 KB Output is correct
10 Correct 720 ms 18772 KB Output is correct
11 Correct 348 ms 19792 KB Output is correct
12 Correct 350 ms 18256 KB Output is correct
13 Correct 0 ms 444 KB Output is correct
14 Correct 85 ms 14064 KB Output is correct
15 Correct 42 ms 1568 KB Output is correct
16 Correct 717 ms 19128 KB Output is correct
17 Correct 374 ms 18492 KB Output is correct
18 Correct 370 ms 18336 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 644 KB Output is correct
5 Correct 6 ms 748 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 84 ms 13872 KB Output is correct
9 Correct 269 ms 7544 KB Output is correct
10 Correct 718 ms 18764 KB Output is correct
11 Correct 357 ms 19900 KB Output is correct
12 Correct 350 ms 18260 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 100 ms 13956 KB Output is correct
15 Correct 41 ms 1616 KB Output is correct
16 Correct 768 ms 19080 KB Output is correct
17 Correct 362 ms 18528 KB Output is correct
18 Correct 344 ms 18512 KB Output is correct
19 Execution timed out 3019 ms 25904 KB Time limit exceeded
20 Halted 0 ms 0 KB -