Submission #129728

#	Time	Username	Problem	Language	Result	Execution time	Memory
129728		pr3pony	Strange Device (APIO19_strange_device)	C++14	100 / 100	1257 ms	63660 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
typedef pair<ll,ll> pll;
#define R first
#define L second
set<pll> s;
void add(pll p)
{
    for (auto it = s.lower_bound({p.L,-1}); it != end(s) && it->L <= p.R; s.erase(it++)) {
        p.L = min(p.L, it->L);
        p.R = max(p.R, it->R);
    }
    s.insert(p);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll A,B,ans=0;
    cin >> n >> A >> B;
    A /= __gcd(A,B+1);
    if (A > inf / B) {
        while (n--) {
            ll l,r;
            cin >> l >> r;
            ans += r - l + 1;
        }
    } else {
        ll C = A * B;
        while (n--) {
            ll l,r;
            cin >> l >> r;
            if (r - l + 1 >= C) {
                add({C-1,0});
            } else {
                l %= C, r %= C;
                if (l <= r)
                    add({r,l});
                else
                    add({C-1,l}), add({r,0});
            }
        }
        for (auto p : s)
            ans += p.R - p.L + 1;
    }
    cout << ans << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30