#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename dataType>
using ordered_set = tree<dataType, null_type, less<dataType>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename dataType1, typename dataType2>
using ordered_map = tree<dataType1, dataType2, less<dataType1>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long double ld;
typedef unsigned ui;
typedef long long lli;
typedef unsigned long long ulli;
typedef vector<int32_t> vi;
typedef vector<ld> vld;
typedef vector<ui> vui;
typedef vector<lli> vlli;
typedef vector<ulli> vulli;
typedef list<int32_t> lsi;
typedef list<ld> lsld;
typedef list<ui> lsui;
typedef list<lli> lslli;
typedef list<ulli> lsulli;
typedef set<int32_t> si;
typedef set<ld> sld;
typedef set<ui> sui;
typedef set<lli> slli;
typedef set<ulli> sulli;
typedef pair<lli, lli> pii;
typedef pair<lli, lli> pll;
#define int int64_t
#define endl "\n"
#define inp(n) int n; cin >> n
#define Inp(n) lli n; cin >> n
#define inpstr(s) string s; cin >> s
#define inp2(a,b) int a,b; cin >> a >> b
#define Inp2(a,b) lli a,b; cin >> a >> b
#define inparr(arr,n) int arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define Inparr(arr,n) lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define f0(i,n) for(int32_t i = 0; i < (n); i++)
#define f1(i,n) for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r) for(int32_t i=(l); i < (r); i++)
#define rep1(i,l,r) for(int32_t i=(l); i <= (r); i++)
#define testIn cin >> test
#define tests for(int32_t testNo=1; testNo <= (test); testNo++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define asrt(v) sort(all(v))
#define dsrt(v) sort(rall(v))
#define revStr(str) string(rall(str))
#define len(a) ((int64_t)(a).size())
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define lcm(a, b) (((a)*(b))/gcd(a,b))
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
#define maxi maximize
#define mini minimize
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define finish return 0
#define clean fflush(stdout)
#define Inf (int32_t)(1e9)
#define INF (lli)(1e18)
#define Eps (ld)(1e-9)
#define EPS (ld)(1e-18)
#define PI (ld)(3.141592653589793238462643383279502884197169L)
#define MOD (int32_t)(1e9+7)
#define MXN (int32_t)(1e5+7)
template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}
template<typename dataType>
inline void maximize(dataType &a, dataType b) {if (a < b) a = b;}
template<typename dataType>
inline void minimize(dataType &a, dataType b) {if (a > b) a = b;}
template<typename dataType>
dataType partitionProbDiff(dataType* arr, dataType n) {
dataType sum = 0;
for (int32_t i = 0; i < n; i++) sum += arr[i];
bool dp[n + 1][sum + 1];
for (int32_t i = 0; i <= n; i++) dp[i][0] = true;
for (int32_t i = 1; i <= sum; i++) dp[0][i] = false;
for (int32_t i = 1; i <= n; i++) {
for (int32_t j = 1; j <= sum; j++) {
dp[i][j] = dp[i - 1][j];
if (arr[i - 1] <= j)
dp[i][j] |= dp[i - 1][j - arr[i - 1]];
}
}
for (int32_t j = sum / 2; j >= 0; j--) {
if (dp[n][j] == true) {
return (sum - 2 * j);
}
}
}
template<typename dataType>
bool subsetSumProblem(dataType set[], dataType n, dataType sum) {
bool subset[n + 1][sum + 1];
for (int32_t i = 0; i <= n; i++)
subset[i][0] = true;
for (int32_t i = 1; i <= sum; i++)
subset[0][i] = false;
for (int32_t i = 1; i <= n; i++) {
for (int32_t j = 1; j <= sum; j++) {
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
}
}
return subset[n][sum];
}
bool isPrefix(string &s, string &y) {
if(s.length() > y.length()) return false;
f0(i, s.length()) if(s[i] != y[i]) return false;
return true;
}
bool ispalindrom(string s) {
f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
return true;
}
template<typename dataType>
dataType gcd(dataType a, dataType b) {
while (b != 0) {
dataType c = b;
b = (lli)a % (lli)b;
a = c;
}
return a;
}
template<typename dataType>
void allPrimeBoolArray(dataType n, bool* prime) {
memset(prime, true, sizeof(prime));
for (int32_t p = 2; p * p <= n; p++) {
if (prime[p]) {
for (dataType i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
template<typename dataType1, typename dataType2>
void allPrimeVector(dataType1 n, dataType2 &primeList) {
bool prime[n+1];
memset(prime, true, sizeof(prime));
for (int32_t p = 2; p * p <= n; p++) {
if (prime[p]) {
for (dataType1 i = p * p; i <= n; i += p)
prime[i] = false;
}
}
for (int32_t p = 2; p <= n; p++)
if (prime[p])
primeList.pb(p);
}
template<typename dataType>
string decimalTokbitsBinary(dataType n,dataType k) {
string s = bitset<64>(n).to_string();
return s.substr(64-k);
}
template<typename dataType>
string decimalToBinary(dataType n) {
string s = bitset<64>(n).to_string();
const auto loc1 = s.find('1');
if(loc1 != string::npos)
return s.substr(loc1);
return "0";
}
template<typename dataType>
dataType val(char c) {
if (c >= '0' && c <= '9')
return (dataType)c - '0';
else
return (dataType)c - 'A' + 10;
}
template<typename dataType>
dataType nthBaseToDecimal(string str, dataType base) {
int32_t len = str.length();
int32_t power = 1;
dataType num = 0;
for (int32_t i = len - 1; i >= 0; i--) {
num += (val<dataType>(str[i]) * power);
power *= base;
}
return num;
}
template<typename dataType>
char reVal(dataType num) {
if (num >= 0 && num <= 9)
return (char)(num + '0');
else
return (char)(num - 10 + 'A');
}
template<typename dataType>
string nthBasefromDeci(dataType inputNum, dataType base) {
string res = "";
while (inputNum > 0) {
res += reVal(inputNum % base);
inputNum /= base;
}
if (res == "")
res = "0";
return revStr(res);
}
template<typename dataType1, typename dataType2>
dataType1 smallFactor(dataType1 n, dataType2 &primes) {
for (dataType1 x:primes) {
if(n % x == 0) {
return x;
break;
} else if (x > sqrt(n)) {
return n;
break;
}
}
return 7;
}
template<typename dataType>
dataType phi(dataType n) {
dataType result = n;
for(int32_t p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0) n /= p;
result -= result / p;
}
}
if (n > 1) result -= result / n;
return result;
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t powMod(dataType1 base, dataType2 n, dataType3 mod) {
if (n == 0) return 1;
if (n % 2 == 0) {
int64_t t_pow = (int64_t)powMod(base, n/2, mod);
return ((t_pow*t_pow) % mod);
}
int64_t t_pow = (int64_t)powMod(base, (n-1)/2, mod);
return ((int64_t)base * ((t_pow*t_pow) % mod) % mod);
}
template<typename dataType1, typename dataType2>
int64_t modInverse(dataType1 n, dataType2 mod, bool isPrime = true) {
if(isPrime) return powMod(n, mod-2, mod);
return powMod(n, phi(mod)-1, mod);
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t modDivide(dataType1 a, dataType2 b, dataType3 mod, bool isPrime = true) {
return (((int64_t)a * modInverse(b, mod, isPrime)) % mod);
}
//define a compare function for pair
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
bool compare(pair<dataType1, dataType2> &a, pair<dataType3, dataType4> &b) {
return a.first < b.first;
}
template<typename dataType>
dataType segtree_operator(dataType a, dataType b) {
return a + b;
}
template<typename dataType>
struct segtree {
int size;
vector<dataType> tree;
dataType init_val;
template<typename dataType1>
segtree(int n, dataType1 &arr, dataType init) {
init_segtree(n, init);
for (int32_t i = 0; i < n; i++) {
tree[size+i] = arr[i];
}
for (int32_t i = size-1; i > 0; i--) {
tree[i] = segtree_operator(tree[i*2], tree[i*2+1]);
}
}
segtree(int n, dataType* arr, dataType init) {
init_segtree(n, init);
for (int32_t i = 0; i < n; i++) {
tree[size+i] = arr[i];
}
for (int32_t i = size-1; i > 0; i--) {
tree[i] = segtree_operator(tree[i*2], tree[i*2+1]);
}
}
void init_segtree(int n, dataType init) {
size = 1;
init_val = init;
while (size < n) size *= 2;
tree.resize(size*2, init_val);
}
void update(int ind, dataType val) {
ind += size;
tree[ind] = val;
while (ind > 1) {
ind /= 2;
tree[ind] = segtree_operator(tree[ind*2], tree[ind*2+1]);
}
}
dataType query(int l, int r) {
l += size;
r += size;
dataType res = init_val;
while (l <= r) {
if (l % 2 == 1) res = segtree_operator(res, tree[l]);
if (r % 2 == 0) res = segtree_operator(res, tree[r]);
l = (l+1) / 2;
r = (r-1) / 2;
}
return res;
}
};
// Varriables & helper functions
int n;
int a, b, t;
set<pair<int,int>> ranges_lr, ranges_rl;
vector<pair<int,int>> ranges;
pair<int, int> process(int x, int y) {
x %= t;
y %= t;
return {x, y};
}
// Solver functions
int32_t solve1(int32_t) {
cin >> n >> a >> b;
int k = a/gcd(a, b+1);
if(ld(b) * ld(k) >= 2e18) {
t = 2e18;
} else t = b*k;
// print(t);
f0(i, n) {
inp2(x, y);
if(y - x >= t) {
print(t);
finish;
}
auto [l, r] = process(x, y);
// print(l, r);
if(l > r) {
ranges_lr.insert({l, t});
ranges_lr.insert({0, r});
ranges_rl.insert({t, l});
ranges_rl.insert({r, 0});
ranges.pb({l, t});
ranges.pb({0, r});
} else {
ranges_lr.insert({l, r});
ranges_rl.insert({r, l});
ranges.pb({l, r});
}
}
asrt(ranges);
for(auto [l, r]:ranges) {
// print(l, r);
if(ranges_lr.find({l, r}) == ranges_lr.end()) {
continue;
}
set<pair<int,int>> temp;
while(true) {
bool have_l = true, have_r = true;
auto it = ranges_lr.lower_bound({l, -INF});
int cnt = 0;
while(it != ranges_lr.end()) {
if(it->first > r) {
break;
}
cnt++;
maxi(r, it->second);
temp.insert(*it);
it++;
}
if(cnt == 0) {
have_l = false;
}
it = ranges_rl.lower_bound({l, -INF});
cnt = 0;
while(it != ranges_rl.end()) {
if(it->first > r) {
break;
}
cnt++;
mini(l, it->second);
temp.insert({it->second, it->first});
it++;
}
if(cnt == 0) {
have_r = false;
}
if(!have_l && !have_r) {
break;
}
for(auto [ll, rr]:temp) {
ranges_lr.erase({ll, rr});
ranges_rl.erase({rr, ll});
}
temp.clear();
}
ranges_lr.insert({l, r});
ranges_rl.insert({r, l});
}
int ans = 0;
for(auto [l, r]:ranges_lr) {
ans += r - l+1;
}
print(min(ans, t));
finish;
}
int32_t solve2(int32_t);
int32_t solve3(int32_t);
int32_t main() {
#if defined __has_include
#if __has_include("LOCAL.hh")
#include "LOCAL.hh"
#endif
#endif
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
using namespace std::chrono;
cout << fixed << setprecision(9);
auto begin = steady_clock::now();
#else
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#endif
// Previous code
// Main code
int32_t test = 1;
// testIn;
tests {
solve1(testNo);
}
#ifdef LOCAL
auto end = steady_clock::now();
cout << "\nTime : "
<< (ld)duration_cast<nanoseconds>
(end - begin).count()/1000000000
<< "s" << endl;
#endif
finish;
}
Compilation message
strange_device.cpp: In function 'bool isPrefix(std::string&, std::string&)':
strange_device.cpp:59:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | #define f0(i,n) for(int32_t i = 0; i < (n); i++)
| ^
strange_device.cpp:168:5: note: in expansion of macro 'f0'
168 | f0(i, s.length()) if(s[i] != y[i]) return false;
| ^~
strange_device.cpp: In function 'bool ispalindrom(std::string)':
strange_device.cpp:59:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | #define f0(i,n) for(int32_t i = 0; i < (n); i++)
| ^
strange_device.cpp:172:5: note: in expansion of macro 'f0'
172 | f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1812 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
1728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1846 ms |
141232 KB |
Output is correct |
| 3 |
Incorrect |
1867 ms |
141340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1846 ms |
141232 KB |
Output is correct |
| 3 |
Incorrect |
1867 ms |
141340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1846 ms |
141232 KB |
Output is correct |
| 3 |
Incorrect |
1867 ms |
141340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
183 ms |
14536 KB |
Output is correct |
| 3 |
Correct |
174 ms |
14528 KB |
Output is correct |
| 4 |
Correct |
2051 ms |
142028 KB |
Output is correct |
| 5 |
Correct |
176 ms |
14368 KB |
Output is correct |
| 6 |
Correct |
173 ms |
14412 KB |
Output is correct |
| 7 |
Correct |
176 ms |
14528 KB |
Output is correct |
| 8 |
Correct |
180 ms |
14528 KB |
Output is correct |
| 9 |
Correct |
186 ms |
14528 KB |
Output is correct |
| 10 |
Correct |
144 ms |
14524 KB |
Output is correct |
| 11 |
Correct |
151 ms |
14528 KB |
Output is correct |
| 12 |
Incorrect |
150 ms |
14524 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1812 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
1728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
