Submission #261513

#	Time	Username	Problem	Language	Result	Execution time	Memory
261513		Kastanda	Strange Device (APIO19_strange_device)	C++11	100 / 100	657 ms	41276 KiB

strange_device

#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
int n;
ll A, B, K;
int main()
{
    scanf("%d%lld%lld", &n, &A, &B);
    ll K = A / __gcd(A, B + 1);
    if ((long double)K * B < 2e18)
        K *= B;
    else
        K = (ll)(2e18);
    vector < pii > vec;
    for (int i = 0; i < n; i ++)
    {
        ll l, r;
        scanf("%lld%lld", &l, &r);
        if (r - l + 1 >= K)
            return !printf("%lld\n", K);
        if (l % K <= r % K)
            vec.pb(pii(l % K, r % K));
        else
            vec.pb(pii(l % K, K - 1)), vec.pb(pii(0, r % K));
    }
    sort(vec.begin(), vec.end());
    ll tot = 0, r = -1;
    for (pii X : vec)
    {
        X.y ++;
        if (r >= X.y)
            continue;
        if (r < X.x)
            r = X.x;
        tot += X.y - r;
        r = X.y;
    }
    return !printf("%lld\n", tot);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%lld%lld", &n, &A, &B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

• 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