# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1095036 | ro9669 | Strange Device (APIO19_strange_device) | C++17 | 336 ms | 69076 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;
typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;
const int maxN = int(2e6)+7;
const ll inf = ll(1e18)+7;
pair<ll , ll> p[maxN] , nxt_p[maxN];
void solve(){
int n; ll a , b;
cin >> n >> a >> b;
for (int i = 1 ; i <= n ; i++) cin >> p[i].fi >> p[i].se;
a /= __gcd(a , b + 1);
if (inf / a < b){
ll ans = 0;
for (int i = 1 ; i <= n ; i++) ans += 1ll * (p[i].se - p[i].fi + 1);
cout << ans << "\n";
}
else{
ll x = a * b;
int num = 0;
for (int i = 1 ; i <= n ; i++){
if (p[i].fi + x - 1 <= p[i].se){
cout << x << "\n";
return;
}
if (p[i].fi % x <= p[i].se % x){
nxt_p[++num] = {p[i].fi % x , p[i].se % x};
}
else{
nxt_p[++num] = {p[i].fi % x , x - 1};
nxt_p[++num] = {0 , p[i].se % x};
}
}
n = num;
sort(nxt_p + 1 , nxt_p + n + 1);
ll ans = 1ll * (nxt_p[1].se - nxt_p[1].fi + 1) , cur = nxt_p[1].se + 1;
for (int i = 2 ; i <= n ; i++){
if (max(cur , nxt_p[i].fi) <= nxt_p[i].se){
ans += nxt_p[i].se - max(cur , nxt_p[i].fi) + 1;
cur = nxt_p[i].se + 1;
}
}
cout << ans << "\n";
}
}
#define name "A"
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(name".INP" , "r")){
freopen(name".INP" , "r" , stdin);
freopen(name".OUT" , "w" , stdout);
}
int t = 1; //cin >> t;
while (t--) solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |