oj.uz

Submission #525745

# Submission time Handle Problem Language Result Execution time Memory
525745 2022-02-12T18:48:42 Z Alex_tz307 Two Antennas (JOI19_antennas) C++17
22 / 100
 415 ms 32560 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;
      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

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

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 25860 KB Output is correct
2 Correct 397 ms 27928 KB Output is correct
3 Correct 263 ms 21612 KB Output is correct
4 Correct 403 ms 27988 KB Output is correct
5 Correct 155 ms 13292 KB Output is correct
6 Correct 384 ms 27996 KB Output is correct
7 Correct 336 ms 29144 KB Output is correct
8 Correct 415 ms 32528 KB Output is correct
9 Correct 50 ms 5128 KB Output is correct
10 Correct 391 ms 32560 KB Output is correct
11 Correct 219 ms 19628 KB Output is correct
12 Correct 377 ms 32512 KB Output is correct
13 Correct 211 ms 31384 KB Output is correct
14 Correct 195 ms 31212 KB Output is correct
15 Correct 192 ms 30192 KB Output is correct
16 Correct 176 ms 30220 KB Output is correct
17 Correct 217 ms 31700 KB Output is correct
18 Correct 207 ms 30508 KB Output is correct
19 Correct 201 ms 30764 KB Output is correct
20 Correct 196 ms 30924 KB Output is correct
21 Correct 189 ms 31400 KB Output is correct
22 Correct 191 ms 30860 KB Output is correct
23 Correct 203 ms 31020 KB Output is correct
24 Correct 177 ms 30072 KB Output is correct

Subtask #4
0 / 65.0

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