Submission #983137

#	Time	Username	Problem	Language	Result	Execution time	Memory
983137		LittleOrange	Strange Device (APIO19_strange_device)	C++17	100 / 100	396 ms	80620 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll big = 1e18;
ll cal(ll a, ll b){
    __int128 g = gcd(a,b+1);
    __int128 x=a,y=b+1,w=b,z,lim = 2e18;
    z = x/g*w;
    if (z>lim) return lim;
    else return z;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,a,b;
    cin >> n >> a >> b;
    ll m = cal(a,b);
    //cout << m << "\n";
    vector<pair<ll,ll>> v;
    while(n--){
        ll l,r;
        cin >> l >> r;
        ll ml = (l+m-1)/m*m;
        ll mr = r/m*m;
        //cout << l << " " << r << " " << ml << " " << mr << "\n";
        if (ml<mr){
            v.push_back({0,m-1});
        }else if (ml>mr){
            v.push_back({l%m,r%m});
        }else{
            if(l%m)v.push_back({l%m,m-1});
            v.push_back({0,r%m});
        }
    }
    sort(v.begin(),v.end());
    //cout << "v:\n";for(auto &o : v) cout << o.first << " " << o.second << "\n";
    vector<pair<ll,ll>> u;
    for(auto &o : v){
        if (u.empty())u.push_back(o);
        else{
            if (u.back().second>=o.first) u.back().second = max(u.back().second,o.second);
            else{
                u.push_back(o);
            }
        }
    }
    //cout << "u:\n";for(auto &o : u) cout << o.first << " " << o.second << "\n";
    ll ans = 0;
    for(auto &o : u) ans += o.second-o.first+1;
    cout << ans << "\n";
}

Compilation message (stderr)

strange_device.cpp: In function 'll cal(ll, ll)':
strange_device.cpp:8:18: warning: unused variable 'y' [-Wunused-variable]
    8 |     __int128 x=a,y=b+1,w=b,z,lim = 2e18;
      |                  ^

• 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