oj.uz

Submission #235668

# Submission time Handle Problem Language Result Execution time Memory
235668 2020-05-29T09:40:46 Z fedoseevtimofey Two Antennas (JOI19_antennas) C++14
0 / 100
 413 ms 39796 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
 
using namespace std;
 
typedef long long ll;

const int N = 2e5 + 7;
const int Inf = 1e9;

struct Tree {
  int mx[4 * N], t[4 * N], mod[4 * N];

  void update(int v, int x) {
    mod[v] = max(mod[v], x);
    mx[v] = max(mx[v], t[v] + mod[v]);
  }

  void push(int v) {
    if (mod[v] != -Inf) {
      if (2 * v + 1 < 4 * N) update(2 * v + 1, mod[v]);
      if (2 * v + 2 < 4 * N) update(2 * v + 2, mod[v]);
      mod[v] = -Inf;
    }
  }

  void modify(int ql, int qr, int val, int l, int r, int v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
      update(v, val);
    } else {
      push(v);
      int m = (l + r) >> 1;
      modify(ql, qr, val, l, m, 2 * v + 1);
      modify(ql, qr, val, m + 1, r, 2 * v + 2);
      t[v] = max(t[2 * v + 1], t[2 * v + 2]);
      mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
    }
  }


  void set_(int id, int val, int l, int r, int v) {
    if (l == r) {
      push(v);
      t[v] = val;
    } else {
      push(v);
      int m = (l + r) >> 1;
      if (id <= m) set_(id, val, l, m, 2 * v + 1);
      else set_(id, val, m + 1, r, 2 * v + 2);
      t[v] = max(t[2 * v + 1], t[2 * v + 2]);
      mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
    }
    t[id] = val;
  }

  int get(int ql, int qr, int l, int r, int v) {
    if (qr < l || r < ql) return -Inf;
    if (ql <= l && r <= qr) return mx[v];
    push(v);
    int m = (l + r) >> 1;
    return max(get(ql, qr, l, m, 2 * v + 1), get(ql, qr, m + 1, r, 2 * v + 2));
  }
  
  Tree() {
    fill(t, t + 4 * N, -Inf);
    fill(mx, mx + 4 * N, -Inf);
    fill(mod, mod + 4 * N, -Inf);
  }
};

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  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];
  }
  int q;
  cin >> q;
  vector <vector <pair <int, int>>> who(n);
  vector <int> ans(q, -1);
  for (int i = 0; i < q; ++i) {
    int ql, qr;
    cin >> ql >> qr;
    --ql, --qr;
    who[qr].emplace_back(ql, i);
  }

  vector <vector <int>> add(n), del(n);
  for (int i = 0; i < n; ++i) {
    int l = i + a[i], r = i + b[i];
    r = min(r, n - 1);
    if (l <= r) {
      add[l].push_back(i);
      del[r].push_back(i);
    }
  }

  Tree pos, neg;

  for (int i = 0; i < n; ++i) {
    for (int id : add[i]) {
      pos.set_(id, h[id], 0, n - 1, 0);
      neg.set_(id, -h[id], 0, n - 1, 0);
    }
    int l = max(0, i - b[i]);
    int r = i - a[i];
    if (l <= r) {
      neg.modify(l, r, h[i], 0, n - 1, 0);
      pos.modify(l, r, -h[i], 0, n - 1, 0);
    }
    for (auto p : who[i]) {
      ans[p.second] = max(ans[p.second], pos.get(p.first, i, 0, n - 1, 0));
      ans[p.second] = max(ans[p.second], neg.get(p.first, i, 0, n - 1, 0));
    }
    for (int id : del[i]) {
      pos.set_(id, -Inf, 0, n - 1, 0);
      neg.set_(id, -Inf, 0, n - 1, 0);
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << ans[i] << '\n';
  }
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 37492 KB Output is correct
2 Correct 413 ms 39668 KB Output is correct
3 Correct 275 ms 33652 KB Output is correct
4 Correct 411 ms 39796 KB Output is correct
5 Correct 174 ms 28796 KB Output is correct
6 Correct 409 ms 39540 KB Output is correct
7 Correct 352 ms 36980 KB Output is correct
8 Correct 409 ms 39668 KB Output is correct
9 Correct 56 ms 22648 KB Output is correct
10 Correct 408 ms 39668 KB Output is correct
11 Correct 240 ms 32248 KB Output is correct
12 Correct 410 ms 39668 KB Output is correct
13 Incorrect 226 ms 37236 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

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