Submission #782392

#	Time	Username	Problem	Language	Result	Execution time	Memory
782392		kebine	Strange Device (APIO19_strange_device)	C++17	100 / 100	393 ms	41204 KiB

strange_device

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int MAX=1e18;
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, a, b; cin >> n >> a >> b;
  int mod;
  if(a/__gcd(a, b+1)>(MAX+b-1)/b) mod=MAX+1;
  else mod=a/__gcd(a, b+1)*b;
  priority_queue<pii, vector<pii>, greater<pii>> to_ans;
  int ans=0;
  while(n--) {
    int l, r; cin >> l >> r;
    if((l+mod-1)/mod*mod+mod-1<=r) {cout << mod << '\n'; return 0;}
    else if((l+mod-1)/mod*mod<=r && l%mod) to_ans.push({l%mod, mod-1}), to_ans.push({0, r%mod});
    else to_ans.push({l%mod, r%mod});
    }
    while(!to_ans.empty()) {
      int l=to_ans.top().first, r=to_ans.top().second;
      to_ans.pop();
      while(!to_ans.empty() && to_ans.top().first<=r) r=max(r, to_ans.top().second), to_ans.pop();
    ans+=r-l+1;
  }
  cout << ans << '\n';
    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