Submission #527096

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
527096	2022-02-17T01:50:52 Z	Leonardo_Paes	Strange Device (APIO19_strange_device)	C++17	35 / 100	678 ms	79228 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(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;
		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	0 ms	208 KB	Output is correct
2	Correct	6 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	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	312 KB	Output is correct
16	Correct	6 ms	1232 KB	Output is correct
17	Correct	67 ms	7136 KB	Output is correct
18	Incorrect	1 ms	208 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 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	364 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	678 ms	79228 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	528 ms	34476 KB	Output is correct
3	Correct	562 ms	34476 KB	Output is correct
4	Correct	517 ms	34340 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	528 ms	34476 KB	Output is correct
3	Correct	562 ms	34476 KB	Output is correct
4	Correct	517 ms	34340 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	531 ms	34492 KB	Output is correct
7	Correct	518 ms	34368 KB	Output is correct
8	Correct	520 ms	34364 KB	Output is correct
9	Correct	582 ms	34496 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	528 ms	34476 KB	Output is correct
3	Correct	562 ms	34476 KB	Output is correct
4	Correct	517 ms	34340 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	51 ms	6852 KB	Output is correct
7	Correct	53 ms	7004 KB	Output is correct
8	Correct	50 ms	6612 KB	Output is correct
9	Correct	50 ms	6460 KB	Output is correct
10	Correct	48 ms	6212 KB	Output is correct
11	Correct	50 ms	5812 KB	Output is correct
12	Correct	48 ms	5368 KB	Output is correct
13	Correct	53 ms	5436 KB	Output is correct
14	Correct	49 ms	5376 KB	Output is correct
15	Correct	56 ms	5460 KB	Output is correct
16	Correct	54 ms	5472 KB	Output is correct
17	Correct	49 ms	5392 KB	Output is correct
18	Correct	514 ms	34224 KB	Output is correct
19	Correct	490 ms	34208 KB	Output is correct
20	Correct	588 ms	34196 KB	Output is correct
21	Correct	56 ms	5428 KB	Output is correct
22	Correct	44 ms	5420 KB	Output is correct
23	Correct	223 ms	27804 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	57 ms	5452 KB	Output is correct
3	Correct	53 ms	5428 KB	Output is correct
4	Correct	610 ms	34196 KB	Output is correct
5	Correct	54 ms	5376 KB	Output is correct
6	Correct	54 ms	5380 KB	Output is correct
7	Correct	52 ms	5428 KB	Output is correct
8	Correct	54 ms	5436 KB	Output is correct
9	Correct	53 ms	5436 KB	Output is correct
10	Correct	55 ms	5360 KB	Output is correct
11	Correct	58 ms	5352 KB	Output is correct
12	Correct	48 ms	5436 KB	Output is correct
13	Correct	56 ms	5436 KB	Output is correct
14	Correct	576 ms	34304 KB	Output is correct
15	Correct	56 ms	5356 KB	Output is correct
16	Correct	472 ms	34252 KB	Output is correct
17	Correct	511 ms	34064 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	0 ms	208 KB	Output is correct
2	Correct	6 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	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	312 KB	Output is correct
16	Correct	6 ms	1232 KB	Output is correct
17	Correct	67 ms	7136 KB	Output is correct
18	Incorrect	1 ms	208 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #527096

Compilation message