Submission #200938

#	Time	Username	Problem	Language	Result	Execution time	Memory
200938		baohiep	Strange Device (APIO19_strange_device)	C++14	100 / 100	641 ms	57684 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MAXT=1e18;

int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n; ll a, b; cin>>n>>a>>b;
  vector<pair<ll,ll>> p(n);
  for (auto &x: p) cin>>x.first>>x.second;

  /** the pair repeats after t=a*b/gcd(a, b+1) **/
  a/=__gcd(a, b+1);
  if (b>MAXT/a) {
    ll ans=0;
    for (auto &x: p) ans+=x.second-x.first+1;
    cout<<ans;
  } else {
    ll t=a*b;
    vector<pair<ll, ll>> p2;
    for (auto &x: p) {
      ll low=x.first-x.first%t;
      ll mid=low+t;
      ll high=x.second-x.second%t;
      if (low==high) {
        p2.emplace_back(x.first%t, x.second%t);
      } else if (mid!=high) {
        cout<<t;
        return 0;
      } else {
        p2.emplace_back(x.first%t, t-1);
        p2.emplace_back(0, x.second%t);
      }
    }
    sort(p2.begin(), p2.end());
    ll ans=0;
    ll last=-1;
    for (auto &x: p2) {
      if (last<x.second) {
        ans+=x.second-max(x.first, last+1)+1;
        last=x.second;
      }
    }
    cout<<ans;
  }
  return 0;
}

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