Submission #1044889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044889		serifefedartar	Strange Device (APIO19_strange_device)	C++17	100 / 100	444 ms	74800 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;

    A = 1e18 / A < B ? 1e18 : 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: 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