Submission #527131

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
527131	2022-02-17T02:30:02 Z	Leonardo_Paes	Strange Device (APIO19_strange_device)	C++17	35 / 100	699 ms	79356 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 + 3);
	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	208 KB	Output is correct
2	Correct	7 ms	1284 KB	Output is correct
3	Correct	7 ms	1220 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	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	316 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	204 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	1284 KB	Output is correct
17	Correct	61 ms	6728 KB	Output is correct
18	Incorrect	1 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	1 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	320 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	699 ms	79356 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	584 ms	34960 KB	Output is correct
3	Correct	577 ms	34612 KB	Output is correct
4	Correct	566 ms	34780 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	584 ms	34960 KB	Output is correct
3	Correct	577 ms	34612 KB	Output is correct
4	Correct	566 ms	34780 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	537 ms	34828 KB	Output is correct
7	Correct	547 ms	34832 KB	Output is correct
8	Correct	514 ms	34812 KB	Output is correct
9	Correct	637 ms	34760 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	584 ms	34960 KB	Output is correct
3	Correct	577 ms	34612 KB	Output is correct
4	Correct	566 ms	34780 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	56 ms	6564 KB	Output is correct
7	Correct	57 ms	6368 KB	Output is correct
8	Correct	58 ms	6852 KB	Output is correct
9	Correct	70 ms	6888 KB	Output is correct
10	Correct	55 ms	6832 KB	Output is correct
11	Correct	68 ms	6632 KB	Output is correct
12	Correct	53 ms	6396 KB	Output is correct
13	Correct	62 ms	6564 KB	Output is correct
14	Correct	57 ms	6420 KB	Output is correct
15	Correct	74 ms	6456 KB	Output is correct
16	Correct	57 ms	6232 KB	Output is correct
17	Correct	66 ms	6464 KB	Output is correct
18	Correct	520 ms	36160 KB	Output is correct
19	Correct	520 ms	36316 KB	Output is correct
20	Correct	653 ms	36184 KB	Output is correct
21	Correct	67 ms	6452 KB	Output is correct
22	Correct	63 ms	6384 KB	Output is correct
23	Correct	237 ms	31588 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	55 ms	6396 KB	Output is correct
3	Correct	57 ms	6400 KB	Output is correct
4	Correct	690 ms	34664 KB	Output is correct
5	Correct	54 ms	6452 KB	Output is correct
6	Correct	55 ms	6404 KB	Output is correct
7	Correct	55 ms	6344 KB	Output is correct
8	Correct	66 ms	6396 KB	Output is correct
9	Correct	53 ms	6484 KB	Output is correct
10	Correct	62 ms	6560 KB	Output is correct
11	Correct	55 ms	6356 KB	Output is correct
12	Correct	53 ms	6364 KB	Output is correct
13	Correct	66 ms	6456 KB	Output is correct
14	Correct	597 ms	34844 KB	Output is correct
15	Correct	71 ms	6268 KB	Output is correct
16	Correct	559 ms	35708 KB	Output is correct
17	Correct	550 ms	35664 KB	Output is correct
18	Incorrect	1 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	208 KB	Output is correct
2	Correct	7 ms	1284 KB	Output is correct
3	Correct	7 ms	1220 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	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	316 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	204 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	1284 KB	Output is correct
17	Correct	61 ms	6728 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #527131

Compilation message