#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define int ll
int k, in_group, groups, a, b;
int get_num(int x) {
int id = x % groups;
return in_group * id + (x - id) / groups;
}
int scanline(vector<pair<int, int>> &ev) {
sort(all(ev));
int cl = -1, balance = 0, res = 0;
for (auto it : ev) {
balance -= it.S;
if (balance == 0) {
res += it.F - cl;
cl = -1;
}
else {
if (cl == -1) {
cl = it.F;
}
}
}
return res;
}
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int slow_solve(int n, int a, int b, vector<pair<int, int>> q) {
set<pair<int, int>> used;
for (auto it : q) {
for (int i = it.F; i <= it.S; i++) {
int x = (i + i / b) % a, y = i % b;
used.insert({x, y});
}
}
return SZ(used);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//while (true) {
int n = 1;
a = 123;
b = rnd() % a;
//cin >> n >> a >> b;
vector<pair<int, int>> q(n);
int lim = 10;
for (auto &it : q) {
//cin >> it.F >> it.S;
it.F = rnd() % lim;
it.S = it.F + rnd() % lim;
}
groups = __gcd(a, b + 1);
in_group = a / groups;
//cout << groups << ' ' << in_group << '\n';
map<int, vector<pair<int, int>>> have;
vector<pair<int, int>> ev;
for (int i = 0; i < n; i++) {
int l = q[i].F, r = q[i].S;
int tl = (l % b == 0 ? l : l + (b - l % b)), tr = (r % b == b - 1 ? r : r - r % b - 1);
int x = ((l - l % b) + ((l - l % b) / b)) % a, y = l % b,
x2 = ((r - r % b) + ((r - r % b) / b)) % a, y2 = r % b;
//cout << i << ' ' << tl << ' ' << tr << '\n';
tr -= b - 1;
if (tl > tr && x == x2) {
//cout << "C0 " << get_num(x) << ' ' << y << ' ' << y2 << '\n';
have[get_num(x)].pb({y, -1ll});
have[get_num(x)].pb({y2 + 1, 1ll});
continue;
}
//cout << "OK " << i << '\n';
if (tl > l) {
//cout << "C1 " << get_num(x) << ' ' << y << '\n';
have[get_num(x)].pb({y, -1ll});
have[get_num(x)].pb({b, 1ll});
}
if (tr < r) {
//cout << "C2 " << get_num(x) << ' ' << y2 << '\n';
have[get_num(x2)].pb({0ll, -1ll});
have[get_num(x2)].pb({y2 + 1, 1ll});
}
if (tl > tr) {
continue;
}
tr += b - 1;
int cx = (tl + tl / b) % a, id = cx % groups, num_in_group = (cx - id) / groups;
int f = get_num((tl + tl / b) % a), s = get_num((tr + tr / b) % a), cnt = (tr - tl + 1) / b;
//cout << i << ' ' << (tl + tl / b) % a << ' ' << (tr + tr / b) % a << ' ' << f << ' ' << s << '\n';
/*if (f <= s) {
cnt = s - f + 1;
}
else {
cnt = in_group - (s - f - 1);
}*/
cnt = min(cnt, in_group);
//cout << "MAIN_C " << f << ' ' << cnt << ' ' << id << ' ' << num_in_group << ' ' << get_num(cx) << '\n';
if (num_in_group + cnt - 1 < in_group) {
ev.pb({get_num(cx), -1});
ev.pb({get_num(cx) + cnt, 1});
}
else {
ev.pb({get_num(cx), -1});
ev.pb({get_num(cx) - num_in_group + in_group, 1});
cnt -= in_group - num_in_group;
ev.pb({get_num(cx) - num_in_group, -1});
ev.pb({get_num(cx) - num_in_group + cnt, 1});
}
}
sort(all(ev));
/*for (auto it : ev) {
cout << "DB " << it.F << ' ' << it.S << '\n';
}*/
int balance = 0, cl = -1, ans = 0;
for (auto it : ev) {
balance -= it.S;
if (balance == 0) {
while (!have.empty() && have.begin()->F < it.F) {
have.erase(have.begin());
}
ans += (it.F - cl) * b;
cl = -1;
}
else if (balance > 0 && cl == -1) {
while (!have.empty() && have.begin()->F < it.F) {
ans += scanline(have.begin()->S);
have.erase(have.begin());
}
cl = it.F;
}
}
//cout << ans << '\n';
for (auto it : have) {
ans += scanline(it.S);
}
/*if (ans != slow_solve(n, a, b, q)) {
cout << "ERROR\n";
cout << n << ' ' << a << ' ' << b << '\n';
for (auto it : q) {
cout << it.F << ' ' << it.S << '\n';
}
cout << ans << ' ' << slow_solve(n, a, b, q) << '\n';
cout << '\n';
exit(0);
}*/
//}
cout << ans << '\n';
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:99:8: warning: unused variable 'f' [-Wunused-variable]
int f = get_num((tl + tl / b) % a), s = get_num((tr + tr / b) % a), cnt = (tr - tl + 1) / b;
^
strange_device.cpp:99:40: warning: unused variable 's' [-Wunused-variable]
int f = get_num((tl + tl / b) % a), s = get_num((tr + tr / b) % a), cnt = (tr - tl + 1) / b;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
