제출 #255844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255844		balbit	Strange Device (APIO19_strange_device)	C++14	100 / 100	1348 ms	83996 KiB

strange_device

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

#define lll __int128
#define ll lll

#define pll pair<ll, ll>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x ){ cerr<<x<<endl; }
template<typename T, typename ...S> void _do(T && x , S&&...y){ cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

ll n,A,B,gg;

ll non_prime_inv(ll a, ll b)
{
	ll b0 = b, t, q;
	ll x0 = 0, x1 = 1;
	if (b == 1) return 1;
	while (a > 1) {
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if (x1 < 0) x1 += b0;
	return x1;
}

pair<ll, ll> pos(ll a, ll b) {
    // get the group for this time
    ll an = ((a - b ) % A + A)%A;
    ll grp = an % gg;
    an /= gg;
    ll K = an * non_prime_inv((B+1)/gg, (A)/gg) %(A/gg);
    return {grp, K * B + b};
}

pair<ll, ll> gt(ll t) {
    return {(t+t/B)%A, t%B};
}

void RD(ll & x) {
    long long int t; cin>>t;
    x = t;
}

signed main(){
    IOS();
    bug(1,2,3);
    RD(n); RD(A); RD(B);
    gg = __gcd(A,B+1);
    vector<pll> mp;
    lll GS = A/gg*(lll)B;
    ll start = 0;
    for (int i = 0; i<n; ++i) {
        ll L, R; RD(L); RD(R);
        if (R-L+1 >= GS) {
            cout<<(long long int )GS<<endl; return 0;
        }
        ++R;
        pll lp=pos((L+L/B)%A, L%B);
        ll Lto = lp.s%GS;
        mp.pb({Lto % GS,1});
        pll rp = pos((R+R/B)%A, R%B);
        ll Rto = rp.s%GS;
        mp.pb({Rto % GS,-1});
        assert(lp.f == rp.f);
//        bug(lp.f, Lto, Rto);
        if (Lto > Rto) {
            ++start;
        }
    }
    sort(ALL(mp));
    mp.pb({GS, 0});
    ll re = 0;
    ll prev = 0;
    for (auto &p : mp) {
        if (start > 0) re += p.f - prev;
        prev = p.f;
        start += p.s;
    }
    cout<<(long long int)re<<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