Submission #1150431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150431		Math4Life2020	Strange Device (APIO19_strange_device)	C++20	100 / 100	588 ms	66384 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using ll = __int128; using pii = pair<ll,ll>;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    long long N1,A1,B1; cin >> N1 >> A1 >> B1;
    ll N=N1,A=A1,B=B1;
    ll P = A*B/gcd(A1,B1+1);
    //if A = B+1:  augment t by B -> augment x by (B+1)%A=0
    //increase by B+1 -> period in A: A/gcd(A,B+1)
    vector<pii> upd; //{x,+1} or {x,-1}
    for (ll i=0;i<N1;i++) {
        long long l1,r1; cin >> l1 >> r1;
        ll l=l1,r=r1;
        r++;
        ll D = l/P;
        l -= P*D;
        r -= P*D;
        if (r>=(2*P)) {
            cout << (long long)P << "\n"; exit(0);
        } else if (r>=P) {
            upd.push_back({l,1});
            upd.push_back({P,-1});
            upd.push_back({0,1});
            upd.push_back({r-P,-1});
        } else {
            upd.push_back({l,1});
            upd.push_back({r,-1});
        }
    }
    sort(upd.begin(),upd.end());
    ll cx = 0; ll nact = 0; ll ans = 0;
    for (pii p0: upd) {
        ll x = p0.first; 
        if (nact>0) {
            ans += (x-cx);
        }
        nact += p0.second;
        cx = x;
    }
    cout << (long long)ans <<"\n";
}

• 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