Submission #1105486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105486		borisAngelov	Strange Device (APIO19_strange_device)	C++17	100 / 100	964 ms	19024 KiB

strange_device

#include <bits/stdc++.h>
 
using namespace std;
 
const long long MAXMOD = 1e18 + 7;
 
int n;
long long a, b;
 
void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
 
int main()
{
    fastIO();
 
    cin >> n >> a >> b;
 
    long long MOD = a / __gcd(a, b + 1);
    bool hasPeriod = true;
 
    if (MAXMOD / MOD < b)
    {
        hasPeriod = false;
    }
    else
    {
        MOD *= b; // a * b / gcd(a, b + 1)
    }
 
    vector<pair<long long, long long>> intervals;
    long long ans = 0;
    bool all = false;
 
    for (int i = 1; i <= n; ++i)
    {
        long long l, r;
        cin >> l >> r;
 
        if (hasPeriod == false)
        {
            ans += (r - l + 1);
        }
        else
        {
            long long newL = l % MOD;
            long long newR = r % MOD;
 
            if (l / MOD == r / MOD)
            {
                intervals.push_back({newL, newR});
            }
            else if (l / MOD + 1 == r / MOD)
            {
                intervals.push_back({newL, MOD - 1});
                intervals.push_back({0, newR});
            }
            else
            {
                all = true;
                ans = MOD;
            }
        }
    }
 
    if (hasPeriod == false)
    {
        cout << ans << endl;
        return 0;
    }
 
    if (all == true)
    {
        cout << ans << endl;
        return 0;
    }
 
    sort(intervals.begin(), intervals.end());
 
    long long from = intervals[0].first, to = intervals[0].second;
 
    for (int i = 1; i < intervals.size() - 1; ++i)
    {
        if (intervals[i].first <= to)
        {
            to = max(to, intervals[i].second);
        }
        else
        {
            ans += (to - from + 1);
            from = intervals[i].first;
            to = intervals[i].second;
        }
    }
 
    if (intervals.back().first <= to)
    {
        to = intervals.back().second;
        ans += (to - from + 1);
    }
    else
    {
        ans += (to - from + 1);
        from = intervals.back().first;
        to = intervals.back().second;
        ans += (to - from + 1);
    }
 
    cout << ans << endl;
 
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 1; i < intervals.size() - 1; ++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