oj.uz

Submission #1089192

# Submission time Handle Problem Language Result Execution time Memory
1089192 2024-09-16T07:13:40 Z LucasLe Wall (IOI14_wall) C++17
61 / 100
 3000 ms 44624 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 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 23 ms 692 KB Output is correct
5 Correct 20 ms 688 KB Output is correct
6 Correct 20 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 130 ms 13908 KB Output is correct
3 Correct 1010 ms 7612 KB Output is correct
4 Correct 2670 ms 18548 KB Output is correct
5 Correct 1195 ms 19684 KB Output is correct
6 Correct 1153 ms 18252 KB Output is correct

Subtask #3
29.0 / 29.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 2 ms 348 KB Output is correct
4 Correct 24 ms 600 KB Output is correct
5 Correct 20 ms 600 KB Output is correct
6 Correct 20 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 93 ms 13904 KB Output is correct
9 Correct 985 ms 7604 KB Output is correct
10 Correct 2468 ms 18544 KB Output is correct
11 Correct 1144 ms 19796 KB Output is correct
12 Correct 1144 ms 18292 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 91 ms 13876 KB Output is correct
15 Correct 145 ms 1564 KB Output is correct
16 Correct 2504 ms 19028 KB Output is correct
17 Correct 1142 ms 18408 KB Output is correct
18 Correct 1156 ms 18516 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 24 ms 692 KB Output is correct
5 Correct 20 ms 600 KB Output is correct
6 Correct 20 ms 700 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 90 ms 13896 KB Output is correct
9 Correct 971 ms 7612 KB Output is correct
10 Correct 2538 ms 18548 KB Output is correct
11 Correct 1164 ms 19792 KB Output is correct
12 Correct 1168 ms 18296 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 86 ms 13956 KB Output is correct
15 Correct 146 ms 1560 KB Output is correct
16 Correct 2551 ms 19056 KB Output is correct
17 Correct 1173 ms 18544 KB Output is correct
18 Correct 1190 ms 18484 KB Output is correct
19 Correct 2972 ms 44496 KB Output is correct
20 Correct 2927 ms 40016 KB Output is correct
21 Correct 2999 ms 44624 KB Output is correct
22 Correct 2910 ms 40064 KB Output is correct
23 Execution timed out 3011 ms 40020 KB Time limit exceeded
24 Halted 0 ms 0 KB -