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 ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const ll inf = 1e18 + 1e17;
const int maxn = 1e6 + 5;
ll l[maxn],r[maxn];
vector <pirll> lst;
void input(int n){
for (int i = 1 ; i <= n ; i++) cin >> l[i] >> r[i];
}
ll get_val(ll A,ll B){
A /= __gcd(A,B + 1);
if (A > inf/B) return inf;
return A * B;
}
void gen_pir(int n,ll T){
for (int i = 1 ; i <= n ; i++){
ll L = l[i],R = r[i];
if (L/T == R/T){
lst.push_back({L % T,R % T});
continue;
}
if (R/T > L/T + 1){
lst.push_back({0,T - 1});
return;
}
ll NL = L + (T - L % T) - 1;
if (NL >= L)
lst.push_back({L % T,NL % T});
ll NR = R - R % T;
lst.push_back({NR % T,R % T});
//L..R
}
}
ll solve(int n,ll T){
gen_pir(n,T);
sort(lst.begin(),lst.end());
ll L = lst[0].fi,R = lst[0].se;
ll res = lst[0].se - lst[0].fi + 1,cur = R;
for (int i = 1 ; i < lst.size() ; i++){
L = lst[i].fi;R = lst[i].se;
if (R > cur) res += R - max(cur + 1,L) + 1;
cur = max(cur,R);
}
return res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;ll A,B;
cin >> n >> A >> B;
input(n);
ll T = get_val(A,B);
cout << solve(n,T);
return 0;
}
Compilation message (stderr)
strange_device.cpp: In function 'long long int solve(int, long long int)':
strange_device.cpp:57:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 1 ; i < lst.size() ; i++){
| ~~^~~~~~~~~~~~
# | 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... |