제출 #1127242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127242		duckindog	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	775 ms	165044 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 500'000 + 10,
          MAX = 1'000'000'000;
int n;
struct Writer { 
  int x, e;
  friend istream& operator >> (istream& is, Writer& rhs) { 
    return is >> rhs.x >> rhs.e;
  }
} w[N];

namespace IT { 
  int f[N << 2];
  void update(int s, int l, int r, int p, int x) { 
    if (p < l || p > r) return;
    if (l == r) { 
      f[s] = x;
      return;
    }
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, p, x); update(s << 1 | 1, mid + 1, r, p, x);
    f[s] = min(f[s << 1], f[s << 1 | 1]);
  }
  int query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return MAX;
    if (u <= l && r <= v) return f[s];
    int mid = (l + r) >> 1;
    return min(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
  }
}

struct ST { 
  int mi[N][19], ma[N][19], lg[N];

  void buildST(const vector<int>& arr) { 
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) mi[i][0] = ma[i][0] = arr[i];
    for (int j = 1; j <= 18; ++j) { 
      for (int i = 1; i <= n - (1 << j) + 1; ++i) { 
        mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
        ma[i][j] = max(ma[i][j - 1], ma[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  int getMin(int l, int r) { 
    int j = lg[r - l + 1];
    return min(mi[l][j], mi[r - (1 << j) + 1][j]);
  }
  int getMax(int l, int r) { 
    int j = lg[r - l + 1];
    return max(ma[l][j], ma[r - (1 << j) + 1][j]);
  }
} SMALL, GREAT;

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> w[i];

  sort(w + 1, w + n + 1, [](const auto& a, const auto& b) { return a.x < b.x; });

  { // build ST 
    vector<int> small(1), great(1);
    for (int i = 1; i <= n; ++i)
      small.push_back(w[i].x - w[i].e), great.push_back(w[i].x + w[i].e);
    SMALL.buildST(small); GREAT.buildST(great);
  }
  
  memset(IT::f, 63, sizeof IT::f);
  IT::update(1, 0, n, 0, 0);
  for (int i = 1; i <= n; ++i) { 
    int lt = i;
    { // go left
      int le = 1, ri = i;
      while (le <= ri) { 
        int mid = (le + ri) >> 1;
        if (SMALL.getMin(mid, i) >= w[i].x - w[i].e) ri = (lt = mid) - 1;
        else le = mid + 1;
      }
    }

    int rt = i;
    { // go right
      int le = i, ri = n;
      while (le <= ri) { 
        int mid = (le + ri) >> 1;
        if (GREAT.getMax(i, mid) <= w[i].x + w[i].e) le = (rt = mid) + 1;
        else ri = mid - 1;
      }
    }
    
    int ret = IT::query(1, 0, n, lt - 1, i - 1) + 1;
    IT::update(1, 0, n, rt, min(IT::query(1, 0, n, rt, rt), ret));
  }

  cout << IT::query(1, 0, n, n, n) << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31