Submission #684293

#	Time	Username	Problem	Language	Result	Execution time	Memory
684293		Alexandruabcde	Strange Device (APIO19_strange_device)	C++14	100 / 100	846 ms	100272 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr LL INF = 1LL * 1e18;

int N;
LL A, B;

LL T;

map <long long, int> mp;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> A >> B;

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

    if (A > INF / B) T = INF;
    else T = A * B;

    for (int i = 1; i <= N; ++ i ) {
        LL L, R;
        cin >> L >> R;

        if (R - L + 1 >= T) {
            cout << T << '\n';
            return 0;
        }

        L = L % T;
        R = R % T;

        if (L <= R) {
            mp[L] ++;
            mp[(R+1)] --;
        }
        else {
            mp[L] ++;
            mp[T] --;
            mp[0] ++;
            mp[(R+1)] --;
        }
    }

    LL last = 0;
    int contor = 0;
    LL ans = 0;

    for (auto it : mp) {
        ans += (it.first - last) * (contor != 0);
        contor += it.second;
        last = it.first;
    }

    cout << ans << '\n';
    return 0;
}

• 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