oj.uz

Submission #525750

# Submission time Handle Problem Language Result Execution time Memory
525750 2022-02-12T19:11:30 Z Alex_tz307 Two Antennas (JOI19_antennas) C++17
22 / 100
 446 ms 28092 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);
    maxSelf(t[x].best, max({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);
    maxSelf(t[x].best, max({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 = -INF;
    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 332 KB Output is correct
3 Incorrect 1 ms 332 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 332 KB Output is correct
3 Incorrect 1 ms 332 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 393 ms 25876 KB Output is correct
2 Correct 412 ms 27912 KB Output is correct
3 Correct 281 ms 21604 KB Output is correct
4 Correct 387 ms 27976 KB Output is correct
5 Correct 176 ms 13288 KB Output is correct
6 Correct 397 ms 27976 KB Output is correct
7 Correct 338 ms 25252 KB Output is correct
8 Correct 405 ms 27972 KB Output is correct
9 Correct 45 ms 4496 KB Output is correct
10 Correct 446 ms 28092 KB Output is correct
11 Correct 219 ms 16840 KB Output is correct
12 Correct 417 ms 27888 KB Output is correct
13 Correct 204 ms 27048 KB Output is correct
14 Correct 198 ms 26680 KB Output is correct
15 Correct 246 ms 25896 KB Output is correct
16 Correct 179 ms 25736 KB Output is correct
17 Correct 243 ms 27064 KB Output is correct
18 Correct 201 ms 26008 KB Output is correct
19 Correct 225 ms 26396 KB Output is correct
20 Correct 246 ms 26408 KB Output is correct
21 Correct 187 ms 26968 KB Output is correct
22 Correct 234 ms 26536 KB Output is correct
23 Correct 205 ms 26632 KB Output is correct
24 Correct 176 ms 25596 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 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -