Submission #1248390

#TimeUsernameProblemLanguageResultExecution timeMemory
1248390avohadoStrange Device (APIO19_strange_device)C++20
10 / 100
295 ms32560 KiB
#include <bits/stdc++.h> using namespace std; #define mod 1000000007 #define maxn 1090005 #define f first #define s second #define ll long long #define pb(x) push_back(x) void solve(){ int n; long long A, B, mx; cin >> n >> A >> B; vector<pair<ll, ll>> v; long long a[n], b[n]; for(int i=0; i<n; i++){ cin >> a[i] >> b[i]; } if((b[n-1]+1)/A<B){ mx=b[n-1]+1; }else{ mx=A*B; } for(int i=0; i<n; i++){ if(b[i]-mx>=a[i]-1){ cout << mx;return; } if(a[i]%mx>b[i]%mx){ v.push_back({0, b[i]%mx});v.push_back({a[i]%mx, mx-1}); }else{ v.push_back({a[i]%mx, b[i]%mx}); } } long long ans=0, l=0; sort(v.begin(), v.end()); for(auto i:v){ l=max(l, i.f); ans+=max(i.s-l+1, 0ll); l=max(l, i.s+1); } cout << ans; } int main(){ cin.tie(nullptr)->sync_with_stdio(0); int t=1; //cin >> t; while(t--){ solve(); cout << "\n"; } 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...