제출 #1198165

#제출 시각아이디문제언어결과실행 시간메모리
1198165hengliaoStrange Device (APIO19_strange_device)C++20
100 / 100
308 ms32700 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define pll pair<ll, ll> #define vll vector<ll> #define pb push_back typedef long long ll; typedef __int128 i128; const ll inf=1e18+5; void solve(){ ll n, a, b; cin>>n>>a>>b; vector<pll> v(n); for(auto &[x, y]:v){ cin>>x>>y; } ll tep=(b%a+1)%a; i128 mod; if(tep==0){ mod=b; } else{ mod=a/__gcd(a, tep); mod*=b; } if(mod>(i128) inf){ ll ans=0; for(auto &[x, y]:v){ ans+=y-x+1; } cout<<ans<<'\n'; return; } vector<pll> dumb; for(auto &[x, y]:v){ if(y-x+1>=mod){ cout<<(ll) mod<<'\n'; return; } ll f=x%mod; ll s=y%mod; if(f>s){ dumb.pb({f, mod-1}); dumb.pb({0, s}); } else{ dumb.pb({f, s}); } } sort(dumb.begin(), dumb.end()); ll ans=0; ll mx=-1; for(auto &[x, y]:dumb){ if(y>mx){ ans+=min(y-x+1, y-mx); mx=y; } } cout<<ans<<'\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...