제출 #1105477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105477		borisAngelov	이상한 기계 (APIO19_strange_device)	C++17	15 / 100	306 ms	19016 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);

    if (MAXMOD / MOD < b)
    {
        MOD = MAXMOD;
    }
    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;

        long long newL = l % MOD;
        long long newR = r % MOD;

        if (r - l + 1 >= MOD)
        {
            cout << MOD << endl;
            return 0;
        }

        if (l / MOD == r / MOD)
        {
            intervals.push_back({newL, newR});
        }
        else
        {
            intervals.push_back({newL, MOD - 1});
            intervals.push_back({0, newR});
        }
    }

    sort(intervals.begin(), intervals.end());

    long long from = intervals[0].first, to = intervals[0].second;

    for (int i = 1; i < intervals.size(); ++i)
    {
        if (intervals[i].first <= to)
        {
            to = intervals[i].second;
        }
        else
        {
            ans += (to - from + 1);
            from = intervals[i].first;
            to = intervals[i].second;
        }
    }

    ans += (to - from + 1);
    cout << ans << endl;

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

strange_device.cpp: In function 'int main()':
strange_device.cpp:67: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]
   67 |     for (int i = 1; i < intervals.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~
strange_device.cpp:36:10: warning: unused variable 'all' [-Wunused-variable]
   36 |     bool all = false;
      |          ^~~

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