Submission #527126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
527126	2022-02-17T02:25:21 Z	Leonardo_Paes	Strange Device (APIO19_strange_device)	C++17	35 / 100	737 ms	78896 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define f first
#define s second
// number x and x + (a / gcd(a, b+1) * b) are equal

ll gcd(ll a, ll b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

bool overflow(ll a, ll b){
	ll v = a*b;
	if(a == v/b) return true;
	return false;
}

const ll inf = 1e18;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;
	ll a, b;
	cin >> n >> a >> b;
	ll aux = a / (gcd(a, b+1));
	bool ok = overflow(aux, b);	
	ll m = (ok ? aux * b : inf + 1);
	vector<pii> v;
	bool mx = 0;
	for(int i=0; i<n; i++){
		ll l, r;
		cin >> l >> r;
		if(r-l+1 > m) mx = 1;
		l = l % m, r = r % m;
		if(n == 1){
			if(mx) cout << m << "\n";
			else cout << r-l+1 << "\n";
			return 0;
		}
		if(l <= r){
			v.push_back({l, r});
			v.push_back({r, inf + 5});
		}
		else{
			v.push_back({l, m-1});
			v.push_back({m-1, inf + 5});
			v.push_back({0, r});
			v.push_back({r, inf + 5});
		}
	}
	if(mx){
		cout << m << "\n";
		return 0;
	}
	multiset<ll> s;
	ll ans = 0;
	sort(v.begin(), v.end());
	for(pii x : v){
		ll l = x.f, r = x.s;
		//cout << l << " " << r << "\n";
		if(r == inf + 5){ // out
			s.erase(s.find(-l));
		}
		else{ // in
			if(s.empty()) ans += r-l+1;
			else{
				ll mxx = -(*s.begin());
				ans += max(0LL, r-mxx);
			}
			s.insert(-r);
		}
	}
	cout << ans << "\n";
	return 0;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	5 ms	1232 KB	Output is correct
3	Correct	6 ms	1232 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	308 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	308 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	312 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	6 ms	1228 KB	Output is correct
17	Correct	76 ms	4912 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Incorrect	1 ms	204 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	737 ms	78896 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	316 KB	Output is correct
2	Correct	588 ms	33656 KB	Output is correct
3	Correct	540 ms	33840 KB	Output is correct
4	Correct	498 ms	33576 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	316 KB	Output is correct
2	Correct	588 ms	33656 KB	Output is correct
3	Correct	540 ms	33840 KB	Output is correct
4	Correct	498 ms	33576 KB	Output is correct
5	Correct	1 ms	316 KB	Output is correct
6	Correct	523 ms	33684 KB	Output is correct
7	Correct	560 ms	33596 KB	Output is correct
8	Correct	515 ms	33684 KB	Output is correct
9	Correct	586 ms	33480 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	316 KB	Output is correct
2	Correct	588 ms	33656 KB	Output is correct
3	Correct	540 ms	33840 KB	Output is correct
4	Correct	498 ms	33576 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	48 ms	4796 KB	Output is correct
7	Correct	52 ms	4768 KB	Output is correct
8	Correct	64 ms	4992 KB	Output is correct
9	Correct	67 ms	4796 KB	Output is correct
10	Correct	52 ms	4780 KB	Output is correct
11	Correct	48 ms	4744 KB	Output is correct
12	Correct	54 ms	4968 KB	Output is correct
13	Correct	58 ms	4936 KB	Output is correct
14	Correct	60 ms	4884 KB	Output is correct
15	Correct	60 ms	4976 KB	Output is correct
16	Correct	56 ms	4800 KB	Output is correct
17	Correct	64 ms	4868 KB	Output is correct
18	Correct	552 ms	33780 KB	Output is correct
19	Correct	550 ms	33752 KB	Output is correct
20	Correct	719 ms	33732 KB	Output is correct
21	Correct	76 ms	4856 KB	Output is correct
22	Correct	54 ms	4904 KB	Output is correct
23	Correct	261 ms	27648 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	58 ms	4892 KB	Output is correct
3	Correct	63 ms	4900 KB	Output is correct
4	Correct	657 ms	33488 KB	Output is correct
5	Correct	56 ms	4860 KB	Output is correct
6	Correct	53 ms	4952 KB	Output is correct
7	Correct	53 ms	4960 KB	Output is correct
8	Correct	71 ms	4864 KB	Output is correct
9	Correct	53 ms	4840 KB	Output is correct
10	Correct	58 ms	4948 KB	Output is correct
11	Correct	58 ms	4896 KB	Output is correct
12	Correct	53 ms	4920 KB	Output is correct
13	Correct	56 ms	4912 KB	Output is correct
14	Correct	621 ms	33496 KB	Output is correct
15	Correct	63 ms	4840 KB	Output is correct
16	Correct	519 ms	33704 KB	Output is correct
17	Correct	521 ms	33528 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	5 ms	1232 KB	Output is correct
3	Correct	6 ms	1232 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	308 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	308 KB	Output is correct
9	Correct	1 ms	312 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	312 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	6 ms	1228 KB	Output is correct
17	Correct	76 ms	4912 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #527126

Compilation message