Submission #467431

#	Time	Username	Problem	Language	Result	Execution time	Memory
467431		SirCovidThe19th	Strange Device (APIO19_strange_device)	C++17	100 / 100	2033 ms	100176 KiB

strange_device

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

#define ll long long
#define inf 2e18

int main(){
    int n; ll a, b, p; cin >> n >> a >> b; map<ll, int> d;
    p = a / __gcd(a, b + 1); p = (p >= inf / b) ? inf : p * b;
    for (int i = 0; i < n; i++){
        ll l, r; cin >> l >> r;
        if (r - l + 1 >= p){ d[0]++, d[p]--; continue; }
        l %= p; r %= p;
        if (l <= r) d[l]++, d[r + 1]--;
        else d[0]++, d[r + 1]--, d[l]++, d[p]--;
    }
    int cnt = 0; ll pre, ans = 0;
    for (auto &val : d){
        if (cnt) ans += val.first - pre;
        cnt += val.second; pre = val.first;
    }
    cout<<ans<<endl;
}

• 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