Submission #527091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
527091	2022-02-17T01:47:32 Z	Leonardo_Paes	Strange Device (APIO19_strange_device)	C++17	35 / 100	680 ms	79024 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

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	204 KB	Output is correct
2	Correct	6 ms	1212 KB	Output is correct
3	Correct	6 ms	1336 KB	Output is correct
4	Correct	0 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	0 ms	204 KB	Output is correct
10	Correct	1 ms	312 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	312 KB	Output is correct
13	Correct	0 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	5 ms	1220 KB	Output is correct
17	Correct	63 ms	7256 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	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Incorrect	0 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	372 KB	Output is correct
4	Correct	2 ms	348 KB	Output is correct
5	Correct	680 ms	79024 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	538 ms	34236 KB	Output is correct
3	Correct	529 ms	34216 KB	Output is correct
4	Correct	489 ms	34232 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	538 ms	34236 KB	Output is correct
3	Correct	529 ms	34216 KB	Output is correct
4	Correct	489 ms	34232 KB	Output is correct
5	Correct	0 ms	316 KB	Output is correct
6	Correct	529 ms	34256 KB	Output is correct
7	Correct	618 ms	34232 KB	Output is correct
8	Correct	521 ms	34168 KB	Output is correct
9	Correct	610 ms	34208 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	538 ms	34236 KB	Output is correct
3	Correct	529 ms	34216 KB	Output is correct
4	Correct	489 ms	34232 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	78 ms	7188 KB	Output is correct
7	Correct	63 ms	7272 KB	Output is correct
8	Correct	56 ms	7204 KB	Output is correct
9	Correct	54 ms	7204 KB	Output is correct
10	Correct	51 ms	7276 KB	Output is correct
11	Correct	55 ms	7244 KB	Output is correct
12	Correct	52 ms	7172 KB	Output is correct
13	Correct	59 ms	7200 KB	Output is correct
14	Correct	51 ms	7216 KB	Output is correct
15	Correct	83 ms	7224 KB	Output is correct
16	Correct	75 ms	7304 KB	Output is correct
17	Correct	57 ms	7240 KB	Output is correct
18	Correct	631 ms	37288 KB	Output is correct
19	Correct	524 ms	37304 KB	Output is correct
20	Correct	627 ms	37348 KB	Output is correct
21	Correct	57 ms	7208 KB	Output is correct
22	Correct	46 ms	7248 KB	Output is correct
23	Correct	240 ms	39564 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	60 ms	7180 KB	Output is correct
3	Correct	57 ms	7172 KB	Output is correct
4	Correct	618 ms	34272 KB	Output is correct
5	Correct	54 ms	7224 KB	Output is correct
6	Correct	57 ms	7248 KB	Output is correct
7	Correct	54 ms	7216 KB	Output is correct
8	Correct	55 ms	7220 KB	Output is correct
9	Correct	54 ms	7216 KB	Output is correct
10	Correct	57 ms	7196 KB	Output is correct
11	Correct	56 ms	7252 KB	Output is correct
12	Correct	49 ms	7212 KB	Output is correct
13	Correct	60 ms	7212 KB	Output is correct
14	Correct	584 ms	34340 KB	Output is correct
15	Correct	58 ms	7220 KB	Output is correct
16	Correct	488 ms	36052 KB	Output is correct
17	Correct	502 ms	36060 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	204 KB	Output is correct
2	Correct	6 ms	1212 KB	Output is correct
3	Correct	6 ms	1336 KB	Output is correct
4	Correct	0 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	0 ms	204 KB	Output is correct
10	Correct	1 ms	312 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	312 KB	Output is correct
13	Correct	0 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	5 ms	1220 KB	Output is correct
17	Correct	63 ms	7256 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #527091

Compilation message