Submission #702785

#	Time	Username	Problem	Language	Result	Execution time	Memory
702785		veehz	Strange Device (APIO19_strange_device)	C++17	0 / 100	5051 ms	48852 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128_t i128;

const int NINF = -1e9;

// 0 -> neg ind, 1 -> pos ind
typedef pair<ll, pair<int, bool>> P;
#define val first
#define idx second.first
#define type second.second

set<P> s;  // no overlaps
vector<pair<ll, ll>> spos;

void insert(ll l, ll r, int cur_index) {
  //   cerr << "insert " << l << " " << r << " " << cur_index << endl;
  do {
    auto lp = lower_bound(s.begin(), s.end(), P(l, {NINF, NINF}));
    if (lp != s.end() && (*lp).val <= r && (*lp).type == 1) {
      cur_index = (*lp).idx;
      s.erase(lp);
    } else {
      s.insert(P(l, {-cur_index, 0}));  // 0 -> open,
      spos[cur_index].first = l;
    }
  } while (false);

  do {
    auto rp = prev(lower_bound(s.begin(), s.end(), P(r + 1, {NINF, NINF})));
    if (abs((*rp).idx) != cur_index && (*rp).type == 0) {
      int his_index = abs((*rp).idx);
      ll his_r = spos[his_index].second;
      s.erase(rp);
      s.erase(P(his_r, {his_index, 1}));
      s.insert(P(his_r, {cur_index, 1}));
      spos[cur_index].second = his_r;
      spos[his_index] = {NINF, NINF};
    } else {
      s.insert(P(r, {cur_index, 1}));
      spos[cur_index].second = r;
    }
  } while (false);

  // remove those in the middle
  //   while (true) {
  //     auto it = s.lower_bound(P(l, {NINF, NINF}));
  //     if (-(*it).idx != cur_index) {
  //       s.erase(it);
  //     } else {
  //       break;
  //     }
  //   }

  while (true) {
    auto it = s.upper_bound(P(l, {-cur_index, 0}));
    if (abs((*it).idx) != cur_index) {
      spos[abs((*it).idx)] = {NINF, NINF};
      s.erase(it);
    } else {
      break;
    }
  }
}

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  vector<pair<ll, ll>> v(n);
  for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
  spos.assign(2 * n + 2, {NINF, NINF});

  ll gc = __gcd(a, b + 1);
  bool smallEnough = (i128(a) / gc * i128(b) <= LONG_LONG_MAX);
  ll cy = smallEnough ? a / gc * b : NINF;

  int next = 0;
  for (int i = 0; i < n; i++) {
    auto& p = v[i];
    ll l = p.first, r = p.second;
    if (smallEnough && r - l + 1 >= cy) {
      //   cerr << "FULL" << endl;
      cout << cy << endl;
      return 0;
    }

    if (smallEnough) {
      l %= cy;
      r %= cy;
      if (l > r) {
        insert(l, cy - 1, next++);
        insert(0, r, next++);
      } else {
        insert(l, r, next++);
      }
    }

    // output set
    // ll cans = 0;
    // cerr << "set: " << endl;
    // for (int j = 0; j < (int)spos.size(); j++) {
    //   if (spos[j].first != NINF) {
    //     cerr << spos[j].first << " " << spos[j].second << " " << j << endl;
    //     cans += spos[j].second - spos[j].first + 1;
    //   }
    // }
    // for (auto& px : s) {
    //   cerr << "{" << px.val << "," << px.idx << "," << px.type << "}";
    // }
    // cerr << endl;
    // cerr << "CUR" << cans << endl;
  }

  ll ans = 0;
  for (int j = 0; j < (int)spos.size(); j++) {
    if (spos[j].first != NINF) {
      ans += spos[j].second - spos[j].first + 1;
    }
  }
  cout << ans << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30