oj.uz

Submission #1089190

# Submission time Handle Problem Language Result Execution time Memory
1089190 2024-09-16T07:11:28 Z LucasLe Wall (IOI14_wall) C++17
8 / 100
 2666 ms 18168 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 = 309;
 
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 0 ms 348 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 600 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 6 ms 604 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 85 ms 13476 KB Output is correct
3 Correct 269 ms 7248 KB Output is correct
4 Incorrect 2598 ms 18148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 7 ms 648 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 6 ms 676 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 13424 KB Output is correct
9 Correct 259 ms 7420 KB Output is correct
10 Incorrect 2507 ms 18004 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.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 7 ms 712 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 82 ms 13652 KB Output is correct
9 Correct 273 ms 7328 KB Output is correct
10 Incorrect 2666 ms 18168 KB Output isn't correct
11 Halted 0 ms 0 KB -