Submission #264028

#	Time	Username	Problem	Language	Result	Execution time	Memory
264028		batmendbar	Strange Device (APIO19_strange_device)	C++14	10 / 100	494 ms	28064 KiB

strange_device

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

const long long N = ((long long) 1e18) + 5;

long long gcd(long long x, long long y) {
    if (x < y) swap(x, y);
    while (y) {
        x %= y;
        swap(x, y);
    }
    return x;
}

vector< pair<int, int> > v;

long long ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n, a, b;
    cin >> n >> a >> b;
    long long aa = a / gcd(a, b + 1);
    long long len;
    if (aa > (N / b)) 
        len = N;
    else len = a * b;
    for (int i = 0; i < n; i++) {
        long long bg, en;
        cin >> bg >> en;
        if (en - bg >= len) {
            cout << len << '\n';
            exit(0);
        }
        bg %= len;
        en %= len;
        if (bg > en) {
            v.push_back(make_pair(bg, len - 1));
            v.push_back(make_pair(0, en));
        } else {
            v.push_back(make_pair(bg, en));
        }
    }
    sort (v.begin(), v.end());
    long long bg = 0, en = -1;
    for (pair<int, int> x : v) {
        long long bgg = x.first;
        long long enn = x.second;
        if (bgg > en) {
            ans += en - bg + 1;
            bg = bgg;
            en = enn;
            continue;
        }
        if (bgg <= en) {
            en = max(en, enn);
        }
    }
    ans += en - bg + 1;
    cout << ans << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 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