Submission #1059804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059804		dpsaveslives	Strange Device (APIO19_strange_device)	C++17	35 / 100	486 ms	89076 KiB

strange_device

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int MAXN = 4e6+10;
ll vals[MAXN];
pair<ll,ll> ranges[MAXN];
ll pref[MAXN];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N; ll A,B; cin >> N >> A >> B;
    ll C = A/gcd(A,B+1)*B;
    int cnt = 0;
    for(int i = 0;i<N;++i){
        ll l,r; cin >> l >> r;
        if(r-l+1 >= C){
            cout << C << "\n";
            return 0;
        }
        l %= C; r %= C;
        if(l <= r){
            ranges[++cnt] = make_pair(l,r);
        }
        else{
            ranges[++cnt] = make_pair(l,C-1);
            ranges[++cnt] = make_pair(0ll,r);
        }
    }
    int m = 0;
    for(int i = 1;i<=cnt;++i){
        vals[++m] = ranges[i].f;
        vals[++m] = ranges[i].s+1;
    }
    sort(vals+1,vals+m+1);
    for(int i = 1;i<=cnt;++i){
        int ind = lower_bound(vals+1,vals+m+1,ranges[i].f)-vals;
        int ind2 = lower_bound(vals+1,vals+m+1,ranges[i].s+1)-vals;
        ++pref[ind]; --pref[ind2];
    }
    ll ans = 0ll;
    for(int i = 1;i<=m;++i){
        pref[i] += pref[i-1];
        if(pref[i]){
            ans += vals[i+1]-vals[i];
        }
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30