제출 #1368776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368776		dl2718281	이상한 기계 (APIO19_strange_device)	C++20	100 / 100	802 ms	16956 KiB

strange_device

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



int main() {
    long n,a,b;
    cin >> n >> a >> b;
    a /= gcd(a,b+1);
    long m;
    if (b > 1000000000000000005/a) {
        m = 1000000000000000005;
    }
    else {
        m = a*b;
    }
    vector<pair<long,long>> v;
    for (long i = 0; i < n; i++) {
        long l,r;
        cin >> l >> r;
        if (r-l+1 >= m) {
            cout << m;
            return 0;
        }
        l %= m;
        r %= m;
        if (l > r) {
            v.push_back({0,r});
            v.push_back({l,m-1});
        }
        else {
            v.push_back({l,r});
        }
    }
    sort(v.begin(),v.end());
    long r = -1;
    long ans = 0;
    for (auto i:v) {
        ans += max((long)0,i.second-max(r+1,i.first)+1);
        r = max(r,i.second);
    }
    cout << ans;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 5 / 5
• 서브태스크 3: 5 / 5
• 서브태스크 4: 5 / 5
• 서브태스크 5: 5 / 5
• 서브태스크 6: 20 / 20
• 서브태스크 7: 20 / 20
• 서브태스크 8: 30 / 30