Submission #980815

#	Time	Username	Problem	Language	Result	Execution time	Memory
980815		Tuanlinh123	Strange Device (APIO19_strange_device)	C++17	100 / 100	565 ms	80564 KiB

strange_device

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll inf=2e18;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, A, B; cin >> n >> A >> B, A=A/__gcd(A, B+1);
    vector <pll> range;
    if (A>inf/B)
    {
        range.resize(n);
        for (pll &i:range) cin >> i.fi >> i.se;
    }
    else
    {
        ll M=A*B;
        for (ll i=0; i<n; i++)
        {
            ll l, r; cin >> l >> r;
            ll bl=l/M, br=r/M;
            if (bl==br) range.pb({l%M, r%M});
            else if (bl+1==br) range.pb({l%M, M-1}), range.pb({0, r%M});
            else range.pb({0, M-1});
        }
    }
    vector <ll> cx;
    for (pll i:range) cx.pb(i.fi), cx.pb(i.se+1);
    sort(cx.begin(), cx.end()), cx.resize(unique(cx.begin(), cx.end())-cx.begin());
    vector <ll> sum(sz(cx), 0);
    for (pll i:range)
    {
        sum[lower_bound(cx.begin(), cx.end(), i.fi)-cx.begin()]++;
        sum[lower_bound(cx.begin(), cx.end(), i.se+1)-cx.begin()]--;
    }
    ll ans=0;
    for (ll i=0, crr=0; i<sz(cx); crr+=sum[i], ans+=(!!crr)*(cx[i+1]-cx[i]), i++) {}
    cout << ans;
}

• 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