oj.uz

답안 #525746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525746 2022-02-12T18:50:28 Z Alex_tz307 Two Antennas (JOI19_antennas) C++17
22 / 100
 403 ms 28016 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

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].mx = max(t[x * 2].mx, t[x * 2 + 1].mx);
    t[x].best = max({t[x].best, t[x * 2].best, t[x * 2 + 1].best, t[x].mx - t[x].mn});
  }

  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].mx = max(t[x * 2].mx, t[x * 2 + 1].mx);
    t[x].best = max({t[x].best, t[x * 2].best, t[x * 2 + 1].best, t[x].mx - t[x].mn});
  }

  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(1, 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';
  }
}

int 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 346 ms 25840 KB Output is correct
2 Correct 384 ms 27992 KB Output is correct
3 Correct 247 ms 21592 KB Output is correct
4 Correct 382 ms 27924 KB Output is correct
5 Correct 157 ms 13368 KB Output is correct
6 Correct 383 ms 27984 KB Output is correct
7 Correct 326 ms 25364 KB Output is correct
8 Correct 380 ms 28016 KB Output is correct
9 Correct 44 ms 4512 KB Output is correct
10 Correct 403 ms 28004 KB Output is correct
11 Correct 228 ms 16840 KB Output is correct
12 Correct 381 ms 27888 KB Output is correct
13 Correct 207 ms 27056 KB Output is correct
14 Correct 195 ms 26624 KB Output is correct
15 Correct 190 ms 25856 KB Output is correct
16 Correct 181 ms 25908 KB Output is correct
17 Correct 216 ms 27252 KB Output is correct
18 Correct 195 ms 26064 KB Output is correct
19 Correct 201 ms 26308 KB Output is correct
20 Correct 195 ms 26456 KB Output is correct
21 Correct 183 ms 26948 KB Output is correct
22 Correct 192 ms 26616 KB Output is correct
23 Correct 203 ms 26548 KB Output is correct
24 Correct 173 ms 25536 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -