Submission #527105

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
527105	2022-02-17T02:00:27 Z	Leonardo_Paes	Strange Device (APIO19_strange_device)	C++17	35 / 100	693 ms	79168 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);
	assert(m != 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	1284 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	312 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	1 ms	316 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	6 ms	1232 KB	Output is correct
17	Correct	59 ms	6712 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	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	332 KB	Output is correct
2	Correct	2 ms	372 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	2 ms	328 KB	Output is correct
5	Correct	690 ms	79168 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	552 ms	34748 KB	Output is correct
3	Correct	561 ms	34544 KB	Output is correct
4	Correct	583 ms	34680 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	552 ms	34748 KB	Output is correct
3	Correct	561 ms	34544 KB	Output is correct
4	Correct	583 ms	34680 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	532 ms	34576 KB	Output is correct
7	Correct	538 ms	34660 KB	Output is correct
8	Correct	486 ms	34552 KB	Output is correct
9	Correct	587 ms	34724 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	552 ms	34748 KB	Output is correct
3	Correct	561 ms	34544 KB	Output is correct
4	Correct	583 ms	34680 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	53 ms	6696 KB	Output is correct
7	Correct	58 ms	6704 KB	Output is correct
8	Correct	57 ms	7224 KB	Output is correct
9	Correct	53 ms	7232 KB	Output is correct
10	Correct	49 ms	7228 KB	Output is correct
11	Correct	53 ms	7072 KB	Output is correct
12	Correct	53 ms	6968 KB	Output is correct
13	Correct	66 ms	7104 KB	Output is correct
14	Correct	57 ms	7016 KB	Output is correct
15	Correct	57 ms	6804 KB	Output is correct
16	Correct	56 ms	6720 KB	Output is correct
17	Correct	51 ms	6636 KB	Output is correct
18	Correct	531 ms	36600 KB	Output is correct
19	Correct	571 ms	36512 KB	Output is correct
20	Correct	657 ms	36580 KB	Output is correct
21	Correct	61 ms	6680 KB	Output is correct
22	Correct	53 ms	6760 KB	Output is correct
23	Correct	288 ms	29924 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	60 ms	6824 KB	Output is correct
3	Correct	72 ms	6744 KB	Output is correct
4	Correct	693 ms	34524 KB	Output is correct
5	Correct	61 ms	6716 KB	Output is correct
6	Correct	55 ms	6764 KB	Output is correct
7	Correct	64 ms	6700 KB	Output is correct
8	Correct	67 ms	6832 KB	Output is correct
9	Correct	57 ms	6872 KB	Output is correct
10	Correct	59 ms	6680 KB	Output is correct
11	Correct	56 ms	6640 KB	Output is correct
12	Correct	55 ms	6840 KB	Output is correct
13	Correct	60 ms	6672 KB	Output is correct
14	Correct	650 ms	34552 KB	Output is correct
15	Correct	58 ms	6716 KB	Output is correct
16	Correct	530 ms	35800 KB	Output is correct
17	Correct	512 ms	34976 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	0 ms	208 KB	Output is correct
2	Correct	6 ms	1284 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	312 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	1 ms	316 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	6 ms	1232 KB	Output is correct
17	Correct	59 ms	6712 KB	Output is correct
18	Incorrect	1 ms	208 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #527105

Compilation message