Submission #1044886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044886		serifefedartar	Strange Device (APIO19_strange_device)	C++17	0 / 100	416 ms	62896 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 3e4 + 100;

#define int long long
set<pair<int,int>> st;
void add_seg(int l, int r) {
    st.insert({l, r});
}

signed main() {
    fast
    ll n, A, B, mx = -1;
    cin >> n >> A >> B;

    if (B < A)
        swap(A, B);
    if (1e18 / A < B ? 1e18 : A / __gcd(A, B + 1) * B) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l, r;
            cin >> l >> r;
            add_seg(l, r);
        }

        for (auto u : st) {
            ans += max(0LL, (u.s - max(mx + 1, u.f)) + 1);
            mx = max(mx, u.s);
        }
        cout << ans << "\n";
        return 0;
    }

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

    bool control = true;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;

        if (r - l + 1 >= A) {
            cout << A << "\n";
            control = false;
        }

        int x = l % A;
        int y = r % A;
        if (y < x) {
            add_seg(x, A-1);
            add_seg(0, y);
        } else
            add_seg(x, y);
    }

    if (!control)
        return 0;

    ll ans = 0;
    for (auto u : st) {
        ans += max(0LL, u.s - max(mx + 1, u.f) + 1);
        mx = max(mx, u.s);
    }
    cout << ans << "\n";
}

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