#include<bits/stdc++.h>
#include<iostream>
#include<stdlib.h>
#include<cmath>
#include <algorithm>
#include<numeric>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<ll> vll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define trav(a,x) for (auto& a: x)
#define fr(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>=(b); i+=(s))
#define mp make_pair
#define pb push_back
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define in insert
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define out(x) cout<<x<<'\n'
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
double pi = 3.141592;
void xd(string str)
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (str != "")
{
//freopen((str + ".in").c_str(), "r", stdin);
//freopen((str + ".out").c_str(), "w", stdout);
}
}
template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}
template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;
constexpr Modular() : value() {}
template <typename U>
Modular(const U& x) {
value = normalize(x);
}
template <typename U>
static Type normalize(const U& x) {
Type v;
if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if (v < 0) v += mod();
return v;
}
const Type& operator()() const { return value; }
template <typename U>
explicit operator U() const { return static_cast<U>(value); }
constexpr static Type mod() { return T::value; }
Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
Modular& operator++() { return *this += 1; }
Modular& operator--() { return *this -= 1; }
Modular operator++(int) { Modular result(*this); *this += 1; return result; }
Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
Modular operator-() const { return Modular(-value); }
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
return *this;
}
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template <typename U = T>
typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(value * rhs.value);
return *this;
}
Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
template <typename U>
friend const Modular<U>& abs(const Modular<U>& v) { return v; }
template <typename U>
friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
template <typename U>
friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
template <typename U>
friend std::istream& operator>>(std::istream& stream, Modular<U>& number);
private:
Type value;
};
template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
assert(b >= 0);
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1) res *= x;
x *= x;
p >>= 1;
}
return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
typename common_type<typename Modular<T>::Type, int64_t>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}
/*
using ModType = int;
struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/
constexpr int md = int(998244353);
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);
Mint C(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
while ((int)fact.size() < n + 1) {
fact.push_back(fact.back() * (int)fact.size());
inv_fact.push_back(1 / fact.back());
}
return fact[n] * inv_fact[k] * inv_fact[n - k];
}
int add(int a, int b, int mod) { return (((a % mod) + (b % mod)) + mod) % mod; }
int sub(int a, int b, int mod) { return (((a % mod) - (b % mod)) + mod) % mod; }
int mul(int a, int b, int mod) { return (((a % mod) * (b % mod)) + mod) % mod; }
int bin(int a, int b, int mod) { int ans = 1; while (b) { if (b & 1) ans = mul(ans, a, mod); a = mul(a, a, mod); b >>= 1; }return ans; }
int inverse(int a, int mod) { return bin(a, mod - 2, mod); }
int divi(int a, int b, int mod) {
return mul(a, inverse(b, mod), mod);
}
ll add(ll a, ll b, ll mod) { return (((a % mod) + (b % mod)) + mod) % mod; }
ll sub(ll a, ll b, ll mod) { return (((a % mod) - (b % mod)) + mod) % mod; }
ll mul(ll a, ll b, ll mod) { return (((a % mod) * (b % mod)) + mod) % mod; }
ll bin(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1) ans = mul(ans, a, mod); a = mul(a, a, mod); b >>= 1; }return ans; }
ll inverse(ll a, ll mod) { return bin(a, mod - 2, mod); }
ll divi(ll a, ll b, ll mod) {
return mul(a, inverse(b, mod), mod);
}
ll ex(int base, int power, int modulo)
{
if (power == 0)
return 1;
ll result = ex(base, power / 2, modulo);
if (power % 2 == 1)
return(((result * result) % modulo) * base) % modulo;
else return (result * result) % modulo;
}
ll exp(int base, int power)
{
if (power == 0)
return 1;
ll result = exp(base, power / 2);
if (power % 2 == 1)
return(result * result) * base;
else return (result * result);
}
int gcd(int a, int b) {
if (b == 0)return a;
else return gcd(b, a % b);
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
ll gcd(ll a, ll b) {
if (b == 0)return a;
else return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return a * b / gcd(a, b);
}
ll fac(int x, ll mod) {
ll factorial = 1;
for (ll i = 1; i <= x; ++i) {
factorial = mul(factorial, i, mod);
}
return factorial % mod;
}
ll npr(int x, int c, ll mod) {
if (x < c) return 0;
if (x == c) return fac(x, mod);
else return divi(fac(x, mod), (fac(x - c, mod)), mod);
}
ll ncr(int x, int c, ll mod) {
if (x < c) return 0;
if (x == c) return 1;
else return divi(fac(x, mod), mul((fac(x - c, mod)), fac(c, mod), mod), mod);
}
void bton(string s) { stoll(s, nullptr, 2); }
bool isPrime(int n)
{
if (n == 2 || n == 3)
return true;
if (n <= 1 || n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
int ceil_int(int first_number, int divider) {
if (first_number % divider == 0) return first_number / divider;
else return first_number / divider + 1;
}
ll ceil_ll(ll first_number, ll divider) {
if (first_number % divider == 0) return first_number / divider;
else return first_number / divider + 1LL;
}
ll chinese(vll num, vll rem) {
vll pp; pp.clear();
ll prod = 1LL;
FOR(i, 0, sz(num))prod *= num[i];
FOR(i, 0, sz(num))pp.push_back(prod / num[i]);
vll inv; inv.clear();
FOR(i, 0, sz(pp)) {
inv.push_back(ex(pp[i], num[i] - 2, num[i]));
}
ll ans = 0LL;
FOR(i, 0, sz(pp)) {
ans = ans % prod + (((rem[i] * pp[i]) % prod) * (inv[i] % prod)) % prod;
ans %= prod;
}
return ans;
}
//ncr(n+k-1,k-1) where a[i]>=0 need to consider the condition where a[i] is positive int or odd or whatever(on this n will change)
vector<int> smallest_factor;
vector<bool> prime;
vector<int> primes;
// Note: this sieve is O(n), but the constant factor is worse than the O(n log log n) sieve due to the multiplication.
void sieve(int maximum) {
maximum = max(maximum, 1);
smallest_factor.assign(maximum + 1, 0);
prime.assign(maximum + 1, true);
prime[0] = prime[1] = false;
primes = {};
for (int i = 2; i <= maximum; i++) {
if (prime[i]) {
smallest_factor[i] = i;
primes.push_back(i);
}
for (int p : primes) {
if (p > smallest_factor[i] || int64_t(i) * p > maximum)
break;
prime[i * p] = false;
smallest_factor[i * p] = p;
}
}
}
long long query_ask(int a, int b) {
cout << "? " << a << ' ' << b << endl;
long long x; cin >> x;
return x;
}
void query_ans(long long a) {
cout << "! " << a << endl;
return;
}
int computeXOR(int n)// from 0 to n-1
{
if (n % 4 == 0)
return n;
if (n % 4 == 1)
return 1;
if (n % 4 == 2)
return n + 1;
return 0;
}
int digit_sum(int g) {
int cnt = 0;
while (g > 0) {
cnt += g % 10;
g /= 10;
}
return cnt;
}
ll inf = 1e18 + 1;
void solve()
{
ll n, a, b; cin >> n >> a >> b;
if (n == 1) {
ll m=inf;
if ((ll)a * (ll)b > (ll)inf) m = inf;
else m = a * b;
ll x, y;
cin >> x >> y;
cout << min(y - x + 1, m);
}
else {
set<pair<ll, ll>> p;
for (int i = 0; i < n; i++) {
ll x, y; cin >> x >> y;
for (ll j = x; j <= y; j++) {
p.insert(make_pair((j + ceil_ll(j, b)) % a, j % b));
}
}
cout << p.size() << '\n';
}
}
int main()
{
xd("");
int t = 1; //cin >> t;
while (t--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
40 ms |
12236 KB |
Output is correct |
| 3 |
Correct |
67 ms |
17932 KB |
Output is correct |
| 4 |
Correct |
2 ms |
852 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
35 ms |
6948 KB |
Output is correct |
| 16 |
Correct |
24 ms |
6736 KB |
Output is correct |
| 17 |
Correct |
51 ms |
6604 KB |
Output is correct |
| 18 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
216 KB |
Output is correct |
| 2 |
Correct |
131 ms |
32276 KB |
Output is correct |
| 3 |
Correct |
158 ms |
32052 KB |
Output is correct |
| 4 |
Correct |
106 ms |
30472 KB |
Output is correct |
| 5 |
Execution timed out |
5089 ms |
62504 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
487 ms |
62948 KB |
Output is correct |
| 3 |
Runtime error |
1661 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
487 ms |
62948 KB |
Output is correct |
| 3 |
Runtime error |
1661 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
487 ms |
62948 KB |
Output is correct |
| 3 |
Runtime error |
1661 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1330 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
40 ms |
12236 KB |
Output is correct |
| 3 |
Correct |
67 ms |
17932 KB |
Output is correct |
| 4 |
Correct |
2 ms |
852 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
468 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
35 ms |
6948 KB |
Output is correct |
| 16 |
Correct |
24 ms |
6736 KB |
Output is correct |
| 17 |
Correct |
51 ms |
6604 KB |
Output is correct |
| 18 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 19 |
Halted |
0 ms |
0 KB |
- |
