Submission #710531

#	Time	Username	Problem	Language	Result	Execution time	Memory
710531		Ronin13	Strange Device (APIO19_strange_device)	C++14	100 / 100	645 ms	53364 KiB

strange_device

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1000001;


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    ll a, b; cin >> a >> b;
    ll l[n + 1], r[n + 1];
    for(int i = 1; i <= n; i++)
        cin >> l[i] >> r[i];
    ll o = 2e18;
    if(o / a < b + 1){
        ll s = 0;
        for(int i = 1; i <= n; i++)
            s += (r[i] - l[i] + 1);
        cout << s << "\n";
        return 0;
    }
    ll x = __gcd(a, b + 1);
    x = a / x * b;
    vector <pll> vec;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(l[i] / x == r[i] / x){
            vec.pb({l[i] % x, 1});
            vec.pb({r[i] % x + 1, -1});
        }
        else{
            vec.pb({l[i] % x, 1});
            vec.pb({x, -1});
            vec.pb({0, 1});
            vec.pb({r[i] % x + 1, -1});
        }
    }
    sort(vec.begin(), vec.end());
    ll ans = 0;
    ll last = -1;
    for(auto to : vec){
        ll x = to.f, y = to.s;
        if(cnt == 0){
            last = x;
        }
        cnt += y;
        if(cnt == 0){
            ans += x - last;
        }
    }
    cout << ans;
    return 0;
}

• 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