Bình luận

• 
  

  0

  

  dtnguyenthehung  đã bình luận lúc 24, Tháng 4, 2025, 11:51

  ai chưa làm được code đây nhé // FlowerOnStone

  include <bits/stdc++.h>

  using namespace std;

  const int MAX_N = 400005; const int INF = 1000000000;

  struct Sign { int x, a, b; Sign(int x = 0, int a = 0, int b = 0) : x(x), a(a), b(b) {} };

  struct SegmentTree { private: int treeSize; vector<int> nodes, leaf; int currentvalue; int merge(int a, int b) { if (a == -INF) { return b; } if (a == INF) { return INF; } if (b == -INF) { return a; } if (b == INF) { return INF; } if (a == b) { return a; } return INF; } void initTree(int id, int low, int high, int initialvalue[]) { if (low == high) { nodes[id] = initialvalue[low]; leaf[low] = id; return; } int mid = (low + high) / 2; initTree(id * 2, low, mid, initialvalue); initTree(id * 2 + 1, mid + 1, high, initialvalue); nodes[id] = merge(nodes[id * 2], nodes[id * 2 + 1]); } int get(int id, int low, int high, int pos) { if (high < pos) { return high + 1; } if (low >= pos) { if (nodes[id] == -INF) { return high + 1; } if (currentvalue == -INF) { if (nodes[id] == -INF) { return high + 1; } if (nodes[id] != INF) { currentvalue = nodes[id]; return high + 1; } } if (nodes[id] == currentvalue) { return high + 1; } } if (low == high) { return low; } int mid = (low + high) / 2; int result = get(id * 2, low, mid, pos); if (result == mid + 1) { result = get(id * 2 + 1, mid + 1, high, pos); } return result; }

  public: void init(int treeSize, int initialvalue[]) { this->treeSize = treeSize; int tmp = 1; while (tmp < treeSize) { tmp *= 2; } nodes.resize(tmp * 2); leaf.resize(treeSize + 1); initTree(1, 1, treeSize, initialvalue); } void update(int pos, int val) { int id = leaf[pos]; nodes[id] = val; while (id > 1) { id /= 2; nodes[id] = merge(nodes[id * 2], nodes[id * 2 + 1]); } } int get(int pos) { current_value = -INF; return get(1, 1, treeSize, pos) - pos; } } smt;

  int n; Sign signs[MAXN]; int nextLeft[MAXN], nextRight[MAXN]; pair<int, int> positions[MAXN]; int basevalue[MAXN];

  void initNextArray() { nextLeft[n] = n + 1; nextRight[n] = n + 1; for (int i = n - 1; i >= 1; i--) { nextLeft[i] = nextLeft[i + 1]; nextRight[i] = nextRight[i + 1]; if (signs[i].x - signs[i].a != signs[i + 1].x - signs[i + 1].a) { nextLeft[i] = i + 1; } if (signs[i].x + signs[i].b != signs[i + 1].x + signs[i + 1].b) { nextRight[i] = i + 1; } } }

  pair<int, int> solve() { sort(positions + 1, positions + n + 1); smt.init(n, basevalue); int left = 1; int maxLength = 0, numChoices = 0; while (left <= n) { int right = left; while (right < n && positions[right + 1].first == positions[left].first) { right++; } for (int i = left; i <= right; i++) { int pos = positions[i].second; smt.update(pos, -INF); } for (int i = left; i <= right; i++) { int tmp = smt.get(positions[i].second); if (tmp > maxLength) { maxLength = tmp; numChoices = 1; } else if (tmp == maxLength) { numChoices++; } } for (int i = left; i <= right; i++) { int pos = positions[i].second; smt.update(pos, basevalue[pos]); } left = right + 1; } return make_pair(maxLength, numChoices); }

  int main() {

  ifdef ONLINE_JUDGE

  freopen("roadsigns.inp", "r", stdin);
  freopen("roadsigns.out", "w", stdout);
  

  endif // ONLINE_JUDGE

  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
      cin >> signs[i].x >> signs[i].a >> signs[i].b;
  }
  initNextArray();
  if (nextLeft[1] == n + 1 || nextRight[1] == n + 1) {
      cout << n << " " << -1 << "\n";
      return 0;
  }
  for (int i = 1; i <= n; i++) {
      positions[i] = make_pair(signs[i].x - signs[i].a, i);
      base_value[i] = signs[i].x + signs[i].b;
  }
  pair&lt;int, int> result = solve();
  for (int i = 1; i <= n; i++) {
      positions[i] = make_pair(signs[i].x + signs[i].b, i);
      base_value[i] = signs[i].x - signs[i].a;
  }
  pair&lt;int, int> tmp = solve();
  if (tmp.first > result.first) {
      result = tmp;
  } else if (tmp.first == result.first) {
      result.second += tmp.second;
  }
  cout << result.first << ' ' << result.second << '\n';
  return 0;
  

  }

• 
  

  -2

  

  tanhphungvivo2009  đã bình luận lúc 13, Tháng 1, 2025, 11:53

  bài khó v?

• 
  

  -2

  

  tanhphungvivo2009  đã bình luận lúc 13, Tháng 1, 2025, 11:53

  hi

• 
  

  -12

  

  LA_NTTANH  đã bình luận lúc 21, Tháng 12, 2024, 13:17

  Úi cái bài này dùng DSU nè! quá tuyệt vời

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.