Submission #947003

#	Time	Username	Problem	Language	Result	Execution time	Memory
947003		biximo	Strange Device (APIO19_strange_device)	C++17	5 / 100	397 ms	52956 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<ll, 2> p2;
int n;
ll A,B;
vector<p2> seq;
bool overs;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> A >> B;
    seq.resize(n);
    overs = (__int128)B*(A/__gcd(A,B+1)) <= 1e18;
    for(auto&[l,r]: seq) {
    	cin >> l >> r;
    }
    if(overs) {
    	ll tp = (A/__gcd(A,B+1))*B;
    	for(int i = 0; i < n; i ++) {
    		auto&[l,r] = seq[i];
    		if(r-l+1>=tp) {
    			cout << tp;
    			return 0;
    		}
    		if(l%tp > r%tp) {
    			seq.push_back({0,r%tp});
    			l %= tp;
    			r = tp-1;
    		} else {
    			l %= tp;
    			r %= tp;
    		}
    	}
    }
    sort(seq.begin(),seq.end());
    ll L = -1, R = -2, ans = 0;
    for(auto[l,r]: seq) {
    	if(l <= R+1) {
    		R = max(R, r);
    	} else {
    		ans += R-L+1;
    		L = l;
    		R = r;
    	}
    }
    ans += R-L+1;
    cout << ans;
}

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