oj.uz

Submission #235675

# Submission time Handle Problem Language Result Execution time Memory
235675 2020-05-29T09:54:52 Z fedoseevtimofey Two Antennas (JOI19_antennas) C++14
0 / 100
 459 ms 32676 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 + 7;

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);
  }
};


vector <int> solve(int n, vector <int> h, vector <int> a, vector <int> b, int q, vector <int> ql, vector <int> qr) {
  vector <vector <pair <int, int>>> who(n);
  vector <int> ans(q, -1);

  for (int i = 0; i < q; ++i) {
    who[qr[i]].emplace_back(ql[i], 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 neg;

  for (int i = 0; i < n; ++i) {
    for (int id : add[i]) {
      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);
    }
    for (auto p : who[i]) {
      ans[p.second] = max(ans[p.second], neg.get(p.first, i, 0, n - 1, 0));
    }
    for (int id : del[i]) {
      neg.set_(id, -Inf, 0, n - 1, 0);
    }
  }
  return ans;
}

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 <int> ql(q), qr(q);
  for (int i = 0; i < q; ++i) {
    cin >> ql[i] >> qr[i];
    --ql[i], --qr[i];
  }
  vector <int> ans = solve(n, h, a, b, q, ql, qr);
  reverse(h.begin(), h.end());
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  for (int i = 0; i < q; ++i) {
    ql[i] = n - ql[i] - 1;
    qr[i] = n - qr[i] - 1;
    swap(ql[i], qr[i]);
  }
  vector <int> rans = solve(n, h, a, b, q, ql, qr);
  for (int i = 0; i < q; ++i) {
    cout << max(ans[i], rans[i]) << '\n';
  }
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 29976 KB Output is correct
2 Correct 434 ms 32368 KB Output is correct
3 Correct 275 ms 25680 KB Output is correct
4 Correct 459 ms 32368 KB Output is correct
5 Correct 178 ms 20216 KB Output is correct
6 Correct 425 ms 32364 KB Output is correct
7 Correct 447 ms 29388 KB Output is correct
8 Correct 457 ms 32676 KB Output is correct
9 Correct 58 ms 13568 KB Output is correct
10 Correct 430 ms 32372 KB Output is correct
11 Correct 241 ms 24132 KB Output is correct
12 Correct 453 ms 32624 KB Output is correct
13 Incorrect 242 ms 31508 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

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