Submission #579496

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579496	2022-06-19T09:23:25 Z	gun_gan	Strange Device (APIO19_strange_device)	C++17	65 / 100	777 ms	127152 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main()
{
	cin.tie(0) -> ios_base::sync_with_stdio(0);
 
	ll n, a, b;
	cin >> n >> a >> b;
 
	if(a > 1e18 / b)
	{
		ll sum = 0;
		for(int i = 0; i < n; i++)
		{
			ll l, r;
			cin >> l >> r;
			sum += r - l + 1;
		}

		cout << sum;
	}
	else
	{
		ll g = a * b / gcd(a, b + 1);

		map<ll, vector<ll>> M;
		for(int i = 0; i < n; i++)
		{
			ll l, r;
			cin >> l >> r;
			l %= g, r %= g;
			if(r < l)
			{
				M[0].push_back(r);
				M[l].push_back(g - 1);
			}
			else
			{
				M[l].push_back(r);
			}
		}
	 
		multiset<ll> S;
		vector<pair<ll,ll>> intervals;
	 
		ll begin = 2e18, last = 0;
		for(auto &[st, v] : M)
		{	
			
			while(!S.empty() && *S.begin() < st)
			{
				S.erase(S.begin());
			}
	 
			if(S.empty() && begin != 2e18)
			{
				intervals.push_back({begin, last});
				begin = 2e18;
				last = 0;
			}
	 
			begin = min(begin, st);
	 
			for(auto i : v)
			{
				S.insert(i);
				last = max(last, i);
			}
	 
		}
	 
		if(!S.empty() && begin != 2e18)
		{
			while(!S.empty())
			{
				last = max(last, *S.begin());
				S.erase(S.begin());
			}
	 
			intervals.push_back({begin, last});
		}
	 
		long long ans = 0;
		for(auto [l, r] : intervals) 
		{
			ans += r - l + 1;
		}
		cout << ans;
	}
 
	
 
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	7 ms	2124 KB	Output is correct
3	Correct	7 ms	2148 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	316 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	316 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	7 ms	2132 KB	Output is correct
17	Correct	66 ms	13896 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	1 ms	388 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	517 ms	55660 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	688 ms	126952 KB	Output is correct
3	Correct	702 ms	127016 KB	Output is correct
4	Correct	725 ms	127140 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	688 ms	126952 KB	Output is correct
3	Correct	702 ms	127016 KB	Output is correct
4	Correct	725 ms	127140 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	738 ms	127152 KB	Output is correct
7	Correct	777 ms	127028 KB	Output is correct
8	Correct	730 ms	127096 KB	Output is correct
9	Correct	773 ms	126924 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	688 ms	126952 KB	Output is correct
3	Correct	702 ms	127016 KB	Output is correct
4	Correct	725 ms	127140 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	69 ms	13872 KB	Output is correct
7	Correct	66 ms	13948 KB	Output is correct
8	Correct	68 ms	13884 KB	Output is correct
9	Correct	72 ms	13960 KB	Output is correct
10	Correct	66 ms	13924 KB	Output is correct
11	Correct	63 ms	13868 KB	Output is correct
12	Correct	63 ms	13948 KB	Output is correct
13	Correct	67 ms	13972 KB	Output is correct
14	Correct	65 ms	13868 KB	Output is correct
15	Correct	71 ms	13852 KB	Output is correct
16	Correct	82 ms	13956 KB	Output is correct
17	Correct	69 ms	13860 KB	Output is correct
18	Correct	664 ms	126924 KB	Output is correct
19	Correct	688 ms	126980 KB	Output is correct
20	Correct	733 ms	126884 KB	Output is correct
21	Correct	67 ms	13844 KB	Output is correct
22	Correct	79 ms	13784 KB	Output is correct
23	Correct	190 ms	19768 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	74 ms	13740 KB	Output is correct
3	Correct	72 ms	13732 KB	Output is correct
4	Correct	759 ms	126924 KB	Output is correct
5	Correct	72 ms	13812 KB	Output is correct
6	Correct	74 ms	13752 KB	Output is correct
7	Correct	73 ms	13796 KB	Output is correct
8	Correct	72 ms	13768 KB	Output is correct
9	Correct	68 ms	13784 KB	Output is correct
10	Correct	65 ms	13768 KB	Output is correct
11	Correct	69 ms	13732 KB	Output is correct
12	Correct	67 ms	13756 KB	Output is correct
13	Correct	83 ms	13796 KB	Output is correct
14	Correct	759 ms	126876 KB	Output is correct
15	Correct	69 ms	13920 KB	Output is correct
16	Correct	687 ms	126608 KB	Output is correct
17	Correct	681 ms	126740 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	7 ms	2124 KB	Output is correct
3	Correct	7 ms	2148 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	316 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	316 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	7 ms	2132 KB	Output is correct
17	Correct	66 ms	13896 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	320 KB	Output is correct
20	Incorrect	1 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #579496

Compilation message