oj.uz

Submission #681627

# Submission time Handle Problem Language Result Execution time Memory
681627 2023-01-13T13:31:15 Z peijar Two Antennas (JOI19_antennas) C++17
22 / 100
 367 ms 56096 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 1e6;
const int INF = 1e18;

int iDeb[MAXN], iFin[MAXN];
int rangeMin[MAXN], rangeMax[MAXN];
int lazyMax[MAXN], lazyMin[MAXN];
int rangeSol[MAXN];

void pull(int node) {
  rangeMin[node] = min(rangeMin[2 * node], rangeMin[2 * node + 1]);
  rangeMax[node] = max(rangeMax[2 * node], rangeMax[2 * node + 1]);

  rangeSol[node] = max(rangeSol[2 * node], rangeSol[2 * node + 1]);
}

void push(int node) {
  if (lazyMax[node] > -INF) {
    int h = lazyMax[node];
    lazyMax[node] = -INF;
    if (iDeb[node] != iFin[node]) {
      lazyMax[2 * node] = max(lazyMax[2 * node], h);
      lazyMax[2 * node + 1] = max(lazyMax[2 * node + 1], h);
    }
    rangeSol[node] = max(rangeSol[node], h - rangeMin[node]);
  }
  if (lazyMin[node] < INF) {
    int h = lazyMin[node];
    lazyMin[node] = INF;
    if (iDeb[node] < iFin[node]) {
      lazyMin[2 * node] = min(lazyMin[2 * node], h);
      lazyMin[2 * node + 1] = min(lazyMin[2 * node + 1], h);
    }
    rangeSol[node] = max(rangeSol[node], rangeMax[node] - h);
  }
}

void build(int node, int l, int r) {
  iDeb[node] = l, iFin[node] = r;
  rangeMin[node] = lazyMin[node] = INF, rangeMax[node] = lazyMax[node] = -INF;
  rangeSol[node] = -INF;

  if (l == r)
    return;
  build(2 * node, l, (l + r) / 2);
  build(2 * node + 1, (l + r) / 2 + 1, r);
}

void update(int node, int pos, int x) {
  push(node);

  if (iDeb[node] > pos or iFin[node] < pos)
    return;
  if (iDeb[node] == iFin[node]) {
    if (x == INF)
      rangeMin[node] = x, rangeMax[node] = -x;
    else
      rangeMin[node] = rangeMax[node] = x;
    return;
  }
  update(2 * node, pos, x);
  update(2 * node + 1, pos, x);
  pull(node);
}

void insert(int node, int l, int r, int x) {
  push(node);
  if (iDeb[node] > r or iFin[node] < l)
    return;
  if (iDeb[node] >= l and iFin[node] <= r) {
    lazyMax[node] = lazyMin[node] = x;
    push(node);
    return;
  }

  insert(2 * node, l, r, x);
  insert(2 * node + 1, l, r, x);
  pull(node);
}

int query(int node, int l, int r) {
  push(node);
  if (iDeb[node] > r or iFin[node] < l)
    return -INF;
  if (iDeb[node] >= l and iFin[node] <= r)
    return rangeSol[node];
  return max(query(2 * node, l, r), query(2 * node + 1, l, r));
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> H(N), A(N), B(N);
  for (int i = 0; i < N; ++i)
    cin >> H[i] >> A[i] >> B[i];

  vector<vector<int>> toInsert(N), toDel(N);
  for (int i = 0; i < N; ++i) {
    if (i - A[i] >= 0)
      toInsert[i - A[i]].push_back(i);
    if (i - B[i] > 0)
      toDel[i - B[i] - 1].push_back(i);
  }

  build(1, 0, N - 1);

  int Q;
  cin >> Q;

  vector<int> sol(Q);
  vector<vector<pair<int, int>>> queries(N);
  for (int i = 0; i < Q; ++i) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    queries[l].emplace_back(r, i);
  }

  for (int i = N - 1; i >= 0; --i) {
    dbg(i);
    for (int j : toInsert[i]) {
      dbg("insert", j);
      update(1, j, H[j]);
    }
    for (int j : toDel[i]) {
      dbg("del", j);
      update(1, j, INF);
    }

    int lo = i + A[i], up = i + B[i];
    if (lo < N) {
      up = min(up, N - 1);
      insert(1, lo, up, H[i]);
    }
    for (auto [r, j] : queries[i])
      sol[j] = query(1, i, r);
    dbg(rangeSol[1], rangeMax[1], rangeMin[1]);
  }
  for (int x : sol) {
    if (x == -INF)
      x = -1;
    cout << x << '\n';
  }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 53408 KB Output is correct
2 Correct 367 ms 56072 KB Output is correct
3 Correct 219 ms 47996 KB Output is correct
4 Correct 333 ms 56076 KB Output is correct
5 Correct 132 ms 27076 KB Output is correct
6 Correct 322 ms 55972 KB Output is correct
7 Correct 283 ms 52472 KB Output is correct
8 Correct 320 ms 55972 KB Output is correct
9 Correct 35 ms 8148 KB Output is correct
10 Correct 326 ms 56096 KB Output is correct
11 Correct 180 ms 31596 KB Output is correct
12 Correct 328 ms 55960 KB Output is correct
13 Correct 175 ms 55568 KB Output is correct
14 Correct 165 ms 55328 KB Output is correct
15 Correct 161 ms 54336 KB Output is correct
16 Correct 159 ms 53784 KB Output is correct
17 Correct 186 ms 55700 KB Output is correct
18 Correct 174 ms 54552 KB Output is correct
19 Correct 172 ms 55084 KB Output is correct
20 Correct 175 ms 55408 KB Output is correct
21 Correct 162 ms 55672 KB Output is correct
22 Correct 165 ms 55180 KB Output is correct
23 Correct 180 ms 55296 KB Output is correct
24 Correct 153 ms 53956 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -