Submission #706121

#	Time	Username	Problem	Language	Result	Execution time	Memory
706121		heavylightdecomp	Strange Device (APIO19_strange_device)	C++14	100 / 100	1961 ms	77780 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a,b;
const int inf = 2e18+5;
#define gcd(a,b) __gcd(a,b)
signed main() {
    cin >> n >> a >> b;
    int p;
    if(a/gcd(a,b+1) > inf/b) {
        p = inf;
    } else {
        p = a / gcd(a,b+1) * b;
    }
    vector<pair<int,int>> range;
    for(int i = 0; i < n; i++) {
        int l,r; cin >> l >> r;
        if(r-l >= p) {
            range.push_back({0,p-1});
        } else {
            l = l % p, r = r % p;
            if(l > r) {
                range.push_back({l, p-1});
                range.push_back({0, r});
            } else {
                range.push_back({l,r});
            }
        }
    }
    sort(begin(range), end(range));
    vector<pair<int,int>> jake;
    for(auto it : range) {
        if(jake.empty() or jake.back().second < it.first) {
            jake.push_back(it);
        } else {
            jake.back().second = max(jake.back().second, it.second);
        }
    }
    int res = 0;
    for(auto it : jake) res += it.second - it.first + 1;
    cout << res <<'\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