Submission #198260

#	Time	Username	Problem	Language	Result	Execution time	Memory
198260		Alexa2001	Strange Device (APIO19_strange_device)	C++17	100 / 100	751 ms	93628 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Nmax = 1e6 + 5;
const ll inf = 1e18 + 10;


struct seg
{
    ll l, r;
} a[Nmax];

ll A, B, per;
int n;

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    int i;
    cin >> n >> A >> B;
    for(i=1; i<=n; ++i) cin >> a[i].l >> a[i].r;

    ll g = __gcd(A, B+1);
    A /= g;

    /// if(A*B > inf)
    if(A > inf / B + 1) per = inf;
        else per = min(inf, A * B);

    for(i=1; i<=n; ++i)
        if(a[i].r - a[i].l + 1 >= per)
        {
            cout << per << '\n';
            return 0;
        }

    vector<pair<ll, ll>> v, v2;

    for(i=1; i<=n; ++i)
    {
        a[i].l %= per;
        a[i].r %= per;

        if(a[i].l <= a[i].r)
            v.push_back({a[i].l, a[i].r});
        else
        {
            v.push_back({a[i].l, per-1});
            v.push_back({0, a[i].r});
        }
    }

    sort(v.begin(), v.end(),
         [](pair<ll,ll> a, pair<ll,ll> b)
         { if(a.first == b.first) return a.second > b.second; return a < b; }
         );

    ll mx = -1;
    for(auto it : v)
        if(it.second > mx) v2.push_back(it), mx = it.second;

    swap(v, v2);

    ll ans = per;

    for(i=0; i+1<v.size(); ++i)
        if(v[i].second < v[i+1].first) ans -= v[i+1].first - v[i].second - 1;

    ans -= v[0].first;
    ans -= per - 1 - v.back().second;

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i+1<v.size(); ++i)
              ~~~^~~~~~~~~

• 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