oj.uz

Submission #525749

# Submission time Handle Problem Language Result Execution time Memory
525749 2022-02-12T18:52:43 Z Alex_tz307 Two Antennas (JOI19_antennas) C++17
22 / 100
 437 ms 38184 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long

using namespace std;

const int kN = 2e5;
int h[1 + kN], a[1 + kN], b[1 + kN], l[1 + kN], r[1 + kN], sol[1 + kN];

struct node {
  int mx, mn, best;
} NIL{-INF, INF, -INF};

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

struct ST {
  int n;
  vector<node> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2, NIL);
  }

  void updateNode(int x, int v) {
    minSelf(t[x].mn, v);
    maxSelf(t[x].best, t[x].mx - t[x].mn);
  }

  void push(int x) {
    if (t[x].mn == INF) {
      return;
    }
    for (int i = 0; i < 2; ++i) {
      updateNode(x * 2 + i, t[x].mn);
    }
    t[x].mn = INF;
  }

  void setMax(int x, int lx, int rx, int pos, int v) {
    if (lx == rx) {
      t[x].mx = v;
      t[x].mn = INF;
      t[x].best = -INF;
      return;
    }
    push(x);
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      setMax(x * 2, lx, mid, pos, v);
    } else {
      setMax(x * 2 + 1, mid + 1, rx, pos, v);
    }
    t[x].best = max({t[x].best, t[x * 2].best, t[x * 2 + 1].best, t[x].mx - t[x].mn});
    t[x].mx = max(t[x * 2].mx, t[x * 2 + 1].mx);
  }

  void setMax(int pos, int v) {
    setMax(1, 1, n, pos, v);
  }

  void updateMin(int x, int lx, int rx, int st, int dr, int v) {
    if (st <= lx && rx <= dr) {
      updateNode(x, v);
      return;
    }
    push(x);
    int mid = (lx + rx) / 2;
    if (st <= mid) {
      updateMin(x * 2, lx, mid, st, dr, v);
    }
    if (mid < dr) {
      updateMin(x * 2 + 1, mid + 1, rx, st, dr, v);
    }
    t[x].best = max({t[x].best, t[x * 2].best, t[x * 2 + 1].best, t[x].mx - t[x].mn});
    t[x].mx = max(t[x * 2].mx, t[x * 2 + 1].mx);
  }

  void updateMin(int st, int dr, int v) {
    updateMin(1, 1, n, st, dr, v);
  }

  int query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x].best;
    }
    push(x);
    int mid = (lx + rx) / 2, ans = -1;
    if (st <= mid) {
      maxSelf(ans, query(x * 2, lx, mid, st, dr));
    }
    if (mid < dr) {
      maxSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
    }
    return ans;
  }

  int query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
};

void solve(int n, int q) {
  vector<vector<int>> queries(n + 1);
  for (int i = 1; i <= q; ++i) {
    queries[r[i]].emplace_back(i);
  }
  vector<vector<int>> enable(n + 1), disable(n + 1);
  ST t(n);
  for (int i = 1; i <= n; ++i) {
    for (int x : enable[i]) {
      t.setMax(x, h[x]);
    }
    for (int x : disable[i]) {
      t.setMax(x, -INF);
    }
    if (i - a[i] >= 1) {
      t.updateMin(max(1LL, i - b[i]), i - a[i], h[i]);
    }
    for (int j : queries[i]) {
      maxSelf(sol[j], t.query(l[j], i));
    }
    if (i + a[i] <= n) {
      enable[i + a[i]].emplace_back(i);
    }
    if (i + b[i] + 1 <= n) {
      disable[i + b[i] + 1].emplace_back(i);
    }
  }
}

void testCase() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> h[i] >> a[i] >> b[i];
  }
  int q;
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    cin >> l[i] >> r[i];
    sol[i] = -1;
  }
  solve(n, q);
  reverse(h + 1, h + n + 1);
  reverse(a + 1, a + n + 1);
  reverse(b + 1, b + n + 1);
  for (int i = 1; i <= n; ++i) {
    swap(l[i], r[i]);
    l[i] = n - l[i] + 1;
    r[i] = n - r[i] + 1;
  }
  solve(n, q);
  for (int i = 1; i <= q; ++i) {
    cout << sol[i] << '\n';
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 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 332 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 372 ms 35584 KB Output is correct
2 Correct 425 ms 38160 KB Output is correct
3 Correct 277 ms 30628 KB Output is correct
4 Correct 429 ms 38160 KB Output is correct
5 Correct 180 ms 18300 KB Output is correct
6 Correct 418 ms 38168 KB Output is correct
7 Correct 369 ms 34836 KB Output is correct
8 Correct 433 ms 38136 KB Output is correct
9 Correct 46 ms 5896 KB Output is correct
10 Correct 423 ms 38148 KB Output is correct
11 Correct 239 ms 22476 KB Output is correct
12 Correct 437 ms 38184 KB Output is correct
13 Correct 208 ms 37828 KB Output is correct
14 Correct 195 ms 37712 KB Output is correct
15 Correct 204 ms 37020 KB Output is correct
16 Correct 175 ms 36404 KB Output is correct
17 Correct 216 ms 38012 KB Output is correct
18 Correct 209 ms 36984 KB Output is correct
19 Correct 199 ms 37260 KB Output is correct
20 Correct 198 ms 37396 KB Output is correct
21 Correct 192 ms 38016 KB Output is correct
22 Correct 198 ms 37424 KB Output is correct
23 Correct 196 ms 37508 KB Output is correct
24 Correct 175 ms 36516 KB Output is correct

Subtask #4
0 / 65.0

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