Submission #1182442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182442		Pacybwoah	Strange Device (APIO19_strange_device)	C++20	100 / 100	542 ms	33480 KiB

strange_device

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll a, b;
    cin >> n >> a >> b;
    ll resa = a / gcd(a, b + 1);
    ll res = 2e18;
    if(res / resa >= b) res = min(res, resa * b);
    vector<pair<ll, int>> vec;
    for(int i = 0; i < n; i++){
        ll l, r;
        cin >> l >> r;
        if(r - l + 1 >= res){
            cout << res << "\n";
            return 0;
        }
        l = l % res;
        r = r % res;
        if(l <= r){
            vec.emplace_back(l, 1);
            vec.emplace_back(r + 1, -1);
        }
        else{
            vec.emplace_back(l, 1);
            vec.emplace_back(res, -1);
            vec.emplace_back(0, 1);
            vec.emplace_back(r + 1, -1);
        }
    }
    vec.emplace_back(res, 0);
    ll ans = 0;
    int cnt = 0;
    sort(vec.begin(), vec.end());
    int sz = (int)vec.size();
    for(int i = 0; i < sz; i++){
        if(vec[i].first == res) break;
        cnt += vec[i].second;
        if(cnt > 0){
            ans += vec[i + 1].first - vec[i].first;
        }
    }
    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