Submission #946987

#	Time	Username	Problem	Language	Result	Execution time	Memory
946987		biximo	Strange Device (APIO19_strange_device)	C++17	0 / 100	426 ms	71960 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);
    ll tp = A*B;
    overs = (tp/B == A) && (tp/A == B) && tp <= 1e18;
    for(auto&[l,r]: seq) {
    	cin >> l >> r;
    }
    if(overs) {
    	for(int i = 0; i < n; i ++) {
    		auto&[l,r] = seq[i];
    		if(r>=l+A*B-1) {
    			cout << A*B; 
    			return 0;
    		}
    		if(l%(A*B) > r%(A*B)) {
    			seq.push_back({0,r%(A*B)});
    			l %= (A*B);
    			r = A*B-1;
    		} else {
    			l %= A*B;
    			r %= A*B;
    		}
    	}
    }
    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: 0 / 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