Submission #527123

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
527123	2022-02-17T02:23:43 Z	Leonardo_Paes	Strange Device (APIO19_strange_device)	C++17	35 / 100	660 ms	79324 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;
		//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	6 ms	1216 KB	Output is correct
3	Correct	6 ms	1232 KB	Output is correct
4	Correct	0 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	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	0 ms	308 KB	Output is correct
14	Correct	0 ms	312 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	6 ms	1276 KB	Output is correct
17	Correct	61 ms	6480 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	312 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	312 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	324 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	660 ms	79324 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	312 KB	Output is correct
2	Correct	514 ms	34680 KB	Output is correct
3	Correct	535 ms	34628 KB	Output is correct
4	Correct	506 ms	34620 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	312 KB	Output is correct
2	Correct	514 ms	34680 KB	Output is correct
3	Correct	535 ms	34628 KB	Output is correct
4	Correct	506 ms	34620 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	522 ms	34692 KB	Output is correct
7	Correct	497 ms	34704 KB	Output is correct
8	Correct	520 ms	34688 KB	Output is correct
9	Correct	592 ms	34716 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	312 KB	Output is correct
2	Correct	514 ms	34680 KB	Output is correct
3	Correct	535 ms	34628 KB	Output is correct
4	Correct	506 ms	34620 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	58 ms	6828 KB	Output is correct
7	Correct	57 ms	6716 KB	Output is correct
8	Correct	54 ms	5948 KB	Output is correct
9	Correct	57 ms	6444 KB	Output is correct
10	Correct	80 ms	6032 KB	Output is correct
11	Correct	64 ms	6520 KB	Output is correct
12	Correct	63 ms	6492 KB	Output is correct
13	Correct	77 ms	6416 KB	Output is correct
14	Correct	69 ms	6468 KB	Output is correct
15	Correct	69 ms	6424 KB	Output is correct
16	Correct	60 ms	6728 KB	Output is correct
17	Correct	55 ms	6584 KB	Output is correct
18	Correct	529 ms	36516 KB	Output is correct
19	Correct	485 ms	36364 KB	Output is correct
20	Correct	606 ms	36456 KB	Output is correct
21	Correct	62 ms	6576 KB	Output is correct
22	Correct	47 ms	6512 KB	Output is correct
23	Correct	235 ms	31316 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	59 ms	6708 KB	Output is correct
3	Correct	56 ms	6316 KB	Output is correct
4	Correct	622 ms	34704 KB	Output is correct
5	Correct	57 ms	6584 KB	Output is correct
6	Correct	54 ms	6400 KB	Output is correct
7	Correct	55 ms	6500 KB	Output is correct
8	Correct	62 ms	6448 KB	Output is correct
9	Correct	53 ms	6552 KB	Output is correct
10	Correct	58 ms	6568 KB	Output is correct
11	Correct	55 ms	6364 KB	Output is correct
12	Correct	53 ms	6576 KB	Output is correct
13	Correct	64 ms	6444 KB	Output is correct
14	Correct	596 ms	34816 KB	Output is correct
15	Correct	57 ms	6456 KB	Output is correct
16	Correct	505 ms	35392 KB	Output is correct
17	Correct	552 ms	35204 KB	Output is correct
18	Incorrect	1 ms	288 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	6 ms	1216 KB	Output is correct
3	Correct	6 ms	1232 KB	Output is correct
4	Correct	0 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	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	0 ms	308 KB	Output is correct
14	Correct	0 ms	312 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	6 ms	1276 KB	Output is correct
17	Correct	61 ms	6480 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #527123

Compilation message