#include<bits/stdc++.h>
using namespace std;
ostream& operator<<(ostream &out, string str) {
for(char c : str) out << c;
return out;
}
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
return out << "(" << p.first << ", " << p.second << ")";
}
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
out << "{";
for(auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << "}";
}
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
cerr << a << ", ";
dump(x...);
}
#ifdef DEBUG
# define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
# define debug(...) false
#endif
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
template<class T> int size(T && a) { return a.size(); }
using LL = long long;
using PII = pair<LL, LL>;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
LL A, B;
cin >> n >> A >> B;
LL d = gcd(A, B + 1);
debug(d);
LL q = -1;
if(1e18 / A < B / d) q = 1e18 + 1;
else q = A * B / d;
debug(q);
vector<PII> events;
auto add_interval = [&](LL l, LL r) {
events.emplace_back(l, +1);
events.emplace_back(r + 1, -1);
};
REP(i, n) {
LL l, r;
cin >> l >> r;
LL a = l / q, b = r / q;
if(a != b) {
if(a + 1 < b) {
cout << q << "\n";
return 0;
}
l %= q, r %= q;
add_interval(l, q - 1);
add_interval(0, r);
}
else add_interval(l % q, r % q);
}
LL ans = 0, last = 0, sum = 0;
sort(events.begin(), events.end());
for(auto &e : events) {
if(sum) ans += (e.ST - last);
sum += e.ND;
last = e.ST;
}
cout << ans << "\n";
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:50:10: warning: statement has no effect [-Wunused-value]
debug(d);
^
strange_device.cpp:54:10: warning: statement has no effect [-Wunused-value]
debug(q);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
504 KB |
Output is correct |
2 |
Correct |
10 ms |
1416 KB |
Output is correct |
3 |
Correct |
10 ms |
1400 KB |
Output is correct |
4 |
Correct |
9 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
4 ms |
376 KB |
Output is correct |
16 |
Correct |
10 ms |
1404 KB |
Output is correct |
17 |
Correct |
88 ms |
7272 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
476 KB |
Output is correct |
5 |
Correct |
543 ms |
57140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
910 ms |
69148 KB |
Output is correct |
3 |
Correct |
929 ms |
69092 KB |
Output is correct |
4 |
Correct |
773 ms |
69012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
910 ms |
69148 KB |
Output is correct |
3 |
Correct |
929 ms |
69092 KB |
Output is correct |
4 |
Correct |
773 ms |
69012 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
793 ms |
68972 KB |
Output is correct |
7 |
Correct |
816 ms |
69160 KB |
Output is correct |
8 |
Correct |
770 ms |
69148 KB |
Output is correct |
9 |
Correct |
965 ms |
69040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
910 ms |
69148 KB |
Output is correct |
3 |
Correct |
929 ms |
69092 KB |
Output is correct |
4 |
Correct |
773 ms |
69012 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
75 ms |
7272 KB |
Output is correct |
7 |
Correct |
80 ms |
7388 KB |
Output is correct |
8 |
Correct |
80 ms |
7476 KB |
Output is correct |
9 |
Correct |
78 ms |
7308 KB |
Output is correct |
10 |
Correct |
73 ms |
7272 KB |
Output is correct |
11 |
Correct |
79 ms |
7400 KB |
Output is correct |
12 |
Correct |
75 ms |
7272 KB |
Output is correct |
13 |
Correct |
86 ms |
7272 KB |
Output is correct |
14 |
Correct |
74 ms |
7360 KB |
Output is correct |
15 |
Correct |
87 ms |
7392 KB |
Output is correct |
16 |
Correct |
86 ms |
7432 KB |
Output is correct |
17 |
Correct |
78 ms |
7272 KB |
Output is correct |
18 |
Correct |
803 ms |
69276 KB |
Output is correct |
19 |
Correct |
775 ms |
69072 KB |
Output is correct |
20 |
Correct |
908 ms |
68944 KB |
Output is correct |
21 |
Correct |
89 ms |
7276 KB |
Output is correct |
22 |
Correct |
72 ms |
7272 KB |
Output is correct |
23 |
Correct |
224 ms |
26708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
82 ms |
7272 KB |
Output is correct |
3 |
Correct |
85 ms |
7312 KB |
Output is correct |
4 |
Correct |
1012 ms |
68928 KB |
Output is correct |
5 |
Correct |
84 ms |
7392 KB |
Output is correct |
6 |
Correct |
85 ms |
7392 KB |
Output is correct |
7 |
Correct |
85 ms |
7452 KB |
Output is correct |
8 |
Correct |
97 ms |
7392 KB |
Output is correct |
9 |
Correct |
83 ms |
7280 KB |
Output is correct |
10 |
Correct |
89 ms |
7420 KB |
Output is correct |
11 |
Correct |
87 ms |
7396 KB |
Output is correct |
12 |
Correct |
76 ms |
7400 KB |
Output is correct |
13 |
Correct |
103 ms |
7320 KB |
Output is correct |
14 |
Correct |
893 ms |
68812 KB |
Output is correct |
15 |
Correct |
88 ms |
7392 KB |
Output is correct |
16 |
Correct |
757 ms |
68968 KB |
Output is correct |
17 |
Correct |
805 ms |
68976 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
504 KB |
Output is correct |
2 |
Correct |
10 ms |
1416 KB |
Output is correct |
3 |
Correct |
10 ms |
1400 KB |
Output is correct |
4 |
Correct |
9 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
4 ms |
376 KB |
Output is correct |
16 |
Correct |
10 ms |
1404 KB |
Output is correct |
17 |
Correct |
88 ms |
7272 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
380 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
504 KB |
Output is correct |
26 |
Correct |
3 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
476 KB |
Output is correct |
28 |
Correct |
543 ms |
57140 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
910 ms |
69148 KB |
Output is correct |
31 |
Correct |
929 ms |
69092 KB |
Output is correct |
32 |
Correct |
773 ms |
69012 KB |
Output is correct |
33 |
Correct |
2 ms |
504 KB |
Output is correct |
34 |
Correct |
793 ms |
68972 KB |
Output is correct |
35 |
Correct |
816 ms |
69160 KB |
Output is correct |
36 |
Correct |
770 ms |
69148 KB |
Output is correct |
37 |
Correct |
965 ms |
69040 KB |
Output is correct |
38 |
Correct |
2 ms |
376 KB |
Output is correct |
39 |
Correct |
75 ms |
7272 KB |
Output is correct |
40 |
Correct |
80 ms |
7388 KB |
Output is correct |
41 |
Correct |
80 ms |
7476 KB |
Output is correct |
42 |
Correct |
78 ms |
7308 KB |
Output is correct |
43 |
Correct |
73 ms |
7272 KB |
Output is correct |
44 |
Correct |
79 ms |
7400 KB |
Output is correct |
45 |
Correct |
75 ms |
7272 KB |
Output is correct |
46 |
Correct |
86 ms |
7272 KB |
Output is correct |
47 |
Correct |
74 ms |
7360 KB |
Output is correct |
48 |
Correct |
87 ms |
7392 KB |
Output is correct |
49 |
Correct |
86 ms |
7432 KB |
Output is correct |
50 |
Correct |
78 ms |
7272 KB |
Output is correct |
51 |
Correct |
803 ms |
69276 KB |
Output is correct |
52 |
Correct |
775 ms |
69072 KB |
Output is correct |
53 |
Correct |
908 ms |
68944 KB |
Output is correct |
54 |
Correct |
89 ms |
7276 KB |
Output is correct |
55 |
Correct |
72 ms |
7272 KB |
Output is correct |
56 |
Correct |
224 ms |
26708 KB |
Output is correct |
57 |
Correct |
2 ms |
384 KB |
Output is correct |
58 |
Correct |
82 ms |
7272 KB |
Output is correct |
59 |
Correct |
85 ms |
7312 KB |
Output is correct |
60 |
Correct |
1012 ms |
68928 KB |
Output is correct |
61 |
Correct |
84 ms |
7392 KB |
Output is correct |
62 |
Correct |
85 ms |
7392 KB |
Output is correct |
63 |
Correct |
85 ms |
7452 KB |
Output is correct |
64 |
Correct |
97 ms |
7392 KB |
Output is correct |
65 |
Correct |
83 ms |
7280 KB |
Output is correct |
66 |
Correct |
89 ms |
7420 KB |
Output is correct |
67 |
Correct |
87 ms |
7396 KB |
Output is correct |
68 |
Correct |
76 ms |
7400 KB |
Output is correct |
69 |
Correct |
103 ms |
7320 KB |
Output is correct |
70 |
Correct |
893 ms |
68812 KB |
Output is correct |
71 |
Correct |
88 ms |
7392 KB |
Output is correct |
72 |
Correct |
757 ms |
68968 KB |
Output is correct |
73 |
Correct |
805 ms |
68976 KB |
Output is correct |
74 |
Correct |
2 ms |
376 KB |
Output is correct |
75 |
Correct |
3 ms |
376 KB |
Output is correct |
76 |
Correct |
4 ms |
376 KB |
Output is correct |
77 |
Correct |
2 ms |
380 KB |
Output is correct |
78 |
Correct |
2 ms |
376 KB |
Output is correct |
79 |
Correct |
9 ms |
1400 KB |
Output is correct |
80 |
Correct |
992 ms |
68608 KB |
Output is correct |
81 |
Correct |
1006 ms |
69060 KB |
Output is correct |
82 |
Correct |
918 ms |
69108 KB |
Output is correct |
83 |
Correct |
969 ms |
69220 KB |
Output is correct |
84 |
Correct |
902 ms |
69268 KB |
Output is correct |
85 |
Correct |
886 ms |
69336 KB |
Output is correct |
86 |
Correct |
223 ms |
26836 KB |
Output is correct |
87 |
Correct |
2 ms |
376 KB |
Output is correct |