Submission #1367150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367150		Nxmkxing	Strange Device (APIO19_strange_device)	C++20	5 / 100	169 ms	23892 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<long long, long long>;

const int N = 1e6 + 10;
ll n, a, b, l[N], r[N], ans[N];
vector<ll> vec[N];

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    cin >> n >> a >> b;
    ll m = a * b / gcd(b + 1, a);
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        ll sz = r[i] - l[i] + 1;
        if (sz >= m) {
            cout << m;
            return 0;
        }
        l[i] %= m, r[i] %= m;
        if (l[i] <= r[i]) {
            ans[l[i]]++;
            ans[r[i]+1]--;
        }
        else {
            ans[l[i]]++;
            ans[0]++;
            ans[r[i]+1]--;
        }
    }
    ll total = 0;
    for (ll t = 0; t < m; t++) {
        if (t) ans[t] += ans[t-1];
        if (ans[t] > 0) total++;
    }
    cout << total;
}

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