| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1146259 | vladilius | Strange Device (APIO19_strange_device) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define arr4 array<ll, 4>
struct ST{
struct node{
node *l, *r;
int m; ll c, p;
node(ll x){
l = r = 0;
m = p = 0; c = x;
}
};
ll n;
node *rt;
ST(ll ns){
n = ns;
rt = new node(n);
}
void push(node *v){
if (!(v -> p)) return;
v -> l -> m += v -> p;
v -> r -> m += v -> p;
v -> l -> p += v -> p;
v -> r -> p += v -> p;
v -> p = 0;
}
void add(node *v, ll tl, ll tr, ll l, ll r, int x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
v -> m += x;
v -> p += x;
return;
}
ll tm = (tl + tr) / 2;
if (!(v -> l)) v -> l = new node(tm - tl + 1);
if (!(v -> r)) v -> r = new node(tr - tm);
push(v);
add(v -> l, tl, tm, l, r, x);
add(v -> r, tm + 1, tr, l, r, x);
v -> m = min(v -> l -> m, v -> r -> m);
v -> c = 0;
if (v -> l -> m == v -> m) v -> c += v -> l -> c;
if (v -> r -> m == v -> m) v -> c += v -> r -> c;
};
void add(ll l, ll r, int x){
add(rt, 1, n, l, r, x);
}
ll get(){
ll out = n;
if (!(rt -> m)) out -= rt -> c;
return out;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n; ll a, b; cin>>n>>a>>b;
vector<ll> l(n + 1), r(n + 1);
for (int i = 1; i <= n; i++){
cin>>l[i]>>r[i];
}
vector<arr4> all;
a /= gcd(a, b + 1);
for (int i = 1; i <= n; i++){
ll r1 = r[i] % b, r2 = l[i] % b - 1;
if (r2 == -1) r2 += b;
if (r1 > r2) swap(r1, r2);
vector<pll> f;
if ((r[i] - l[i] + 1) >= b) f.pb({0, b - 1});
else {
ll x = l[i] % b, y = r[i] % b;
if (x <= y){
f.pb({x, y});
}
else {
f.pb({x, b - 1});
f.pb({0, y});
}
}
vector<arr4> pos;
ll L = ceil((long double) * l[i] / b), R = r[i] / b;
pos.pb({0, r1, L, R});
L = ceil((long double) * (l[i] - r2) / b); R = (r[i] - r2) / b;
if (r1 + 1 <= r2) pos.pb({r1 + 1, r2, L, R});
L = ceil((long double) * (l[i] - (r2 + 1)) / b); R = (r[i] - (r2 + 1)) / b;
if (r2 + 1 <= b - 1) pos.pb({r2 + 1, b - 1, L, R});
for (auto [l1, r1, L, R]: pos){
for (auto [l2, r2]: f){
ll l3 = max(l1, l2), r3 = min(r1, r2);
if (l3 <= r3){
all.pb({l3, i, L, R});
all.pb({r3 + 1, i, -1, -1});
}
}
}
}
auto cmp = [&](arr4 x, arr4 y){
if (x[0] != y[0]) return x[0] < y[0];
return x[2] < y[2];
};
sort(all.begin(), all.end(), cmp);
vector<ll> L(n + 1, -1), R(n + 1, -1);
ll out = 0;
int i1 = 0;
ST T(a);
auto add = [&](ll l, ll r, int x){
if ((r - l + 1) >= a){
T.add(1, a, x);
return;
}
l %= a; r %= a;
if (l <= r){
T.add(l + 1, r + 1, x);
return;
}
if (l < a) T.add(l + 1, a, x);
T.add(1, r + 1, x);
};
while (i1 < all.size()){
int j = i1;
while (j < all.size() && all[i1][0] == all[j][0]){
int i = (int) all[j][1];
if (L[i] != -1){
if (L[i] <= R[i]) add(L[i], R[i], -1);
}
L[i] = all[j][2]; R[i] = all[j][3];
if (L[i] != -1 && L[i] <= R[i]) add(L[i], R[i], 1);
j++;
}
ll R = 0;
if (j == all.size()){
R = b - 1;
}
else {
R = all[j][0] - 1;
}
out += 1LL * (R - all[i1][0] + 1) * T.get();
i1 = j;
}
cout<<out<<"\n";
}