#include<bits/stdc++.h>
using namespace std;
template<class T = int>
inline T fast_scan() {
T res = 0;
char tmp;
do {
tmp = getchar();
} while (tmp < '0' || tmp > '9');
while (tmp >= '0' && tmp <= '9') {
res = res * 10 + tmp - '0';
tmp = getchar();
}
return res;
}
//#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define len(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
bool inter(pll a, pll b) {
return max(a.x, b.x) <= min(a.y, b.y);
}
pll unite(pll a, pll b) {
return {min(a.x, b.x), max(a.y, b.y)};
}
struct Event {
ll x;
int type;
ll p;
Event() {}
Event(ll x, int type, ll p) : x(x), type(type), p(p) {}
};
bool operator<(const Event& a, const Event& b) {
return mt(a.x, a.type) < mt(b.x, b.type);
}
vector<Event> evs;
vector<pll> good;
void add_ev(ll l, ll r, ll p) {
evs.eb(l, 0, p);
evs.eb(r + 1, 1, p);
}
bool check(ll x) {
int l = -1, r = len(good);
while (r - l > 1) {
int mid = (l + r) / 2;
if (good[mid].y >= x) r = mid; else l = mid;
}
if (r == len(good)) return 0;
return good[r].x <= x;
}
int32_t main() {
int n = fast_scan();
ll a = fast_scan(), b = fast_scan();
ll period = a / __gcd(a, b + 1);
for (int i = 0; i < n; ++i) {
ll l = fast_scan(), r = fast_scan();
ll block_l = l / b, block_r = r / b;
if (block_l == block_r) {
add_ev(l % b, r % b, block_l % period);
} else {
if (block_r - block_l != 1) {
ll L = (block_l + 1) % period, R = (block_r - 1) % period;
if (L <= R) {
good.eb(L, R);
} else {
good.eb(0, R);
good.eb(L, period - 1);
}
}
add_ev(l % b, b - 1, block_l % period);
add_ev(0, r % b, block_r % period);
}
}
sort(all(evs));
sort(all(good));
vector<pll> st;
for (auto val : good) {
if (!st.empty() && inter(val, st.back())) st.back() = unite(st.back(), val); else st.pb(val);
}
good = st;
map<int, int> cnt;
int have = 0;
ll ans = 0;
for (auto val : good) ans += (val.y - val.x + 1) * b;
for (int i = 0; i + 1 < len(evs); ++i) {
if (!check(evs[i].p)) {
if (evs[i].type == 0) {
++cnt[evs[i].p];
if (cnt[evs[i].p] == 1) ++have;
} else {
--cnt[evs[i].p];
if (cnt[evs[i].p] == 0) --have;
}
}
ans += have * (evs[i + 1].x - evs[i].x);
}
printf("%I64d", ans);
return 0;
}
Compilation message
strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:121:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
printf("%I64d", ans);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
1276 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1111 ms |
94404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1111 ms |
94404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
1111 ms |
94404 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
76 ms |
6632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
1276 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
