Submission #579495

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579495	2022-06-19T09:19:08 Z	gun_gan	Strange Device (APIO19_strange_device)	C++17	65 / 100	787 ms	127520 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;
 
	ll g;
 
	if(a > 1e18 / b)
	{
		g = 1e18 + 2;
	}
	else
	{
		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	0 ms	212 KB	Output is correct
2	Correct	7 ms	2132 KB	Output is correct
3	Correct	7 ms	2132 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 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	212 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	212 KB	Output is correct
16	Correct	7 ms	2136 KB	Output is correct
17	Correct	79 ms	17108 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	256 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	460 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	535 ms	55732 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	735 ms	127520 KB	Output is correct
3	Correct	717 ms	127472 KB	Output is correct
4	Correct	756 ms	127412 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	735 ms	127520 KB	Output is correct
3	Correct	717 ms	127472 KB	Output is correct
4	Correct	756 ms	127412 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	760 ms	127520 KB	Output is correct
7	Correct	701 ms	127380 KB	Output is correct
8	Correct	697 ms	127356 KB	Output is correct
9	Correct	723 ms	127364 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	735 ms	127520 KB	Output is correct
3	Correct	717 ms	127472 KB	Output is correct
4	Correct	756 ms	127412 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	85 ms	17148 KB	Output is correct
7	Correct	73 ms	17092 KB	Output is correct
8	Correct	66 ms	17096 KB	Output is correct
9	Correct	74 ms	17120 KB	Output is correct
10	Correct	85 ms	17068 KB	Output is correct
11	Correct	71 ms	17112 KB	Output is correct
12	Correct	67 ms	17172 KB	Output is correct
13	Correct	69 ms	17100 KB	Output is correct
14	Correct	65 ms	17096 KB	Output is correct
15	Correct	88 ms	17148 KB	Output is correct
16	Correct	76 ms	17064 KB	Output is correct
17	Correct	70 ms	17100 KB	Output is correct
18	Correct	680 ms	127344 KB	Output is correct
19	Correct	710 ms	127276 KB	Output is correct
20	Correct	741 ms	127244 KB	Output is correct
21	Correct	70 ms	17092 KB	Output is correct
22	Correct	74 ms	17080 KB	Output is correct
23	Correct	208 ms	22000 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	74 ms	17160 KB	Output is correct
3	Correct	82 ms	17108 KB	Output is correct
4	Correct	787 ms	127208 KB	Output is correct
5	Correct	73 ms	17140 KB	Output is correct
6	Correct	87 ms	17064 KB	Output is correct
7	Correct	72 ms	17108 KB	Output is correct
8	Correct	69 ms	17136 KB	Output is correct
9	Correct	68 ms	17096 KB	Output is correct
10	Correct	79 ms	17172 KB	Output is correct
11	Correct	93 ms	17072 KB	Output is correct
12	Correct	70 ms	17156 KB	Output is correct
13	Correct	68 ms	17212 KB	Output is correct
14	Correct	743 ms	127336 KB	Output is correct
15	Correct	73 ms	16760 KB	Output is correct
16	Correct	718 ms	127068 KB	Output is correct
17	Correct	685 ms	127136 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	0 ms	212 KB	Output is correct
2	Correct	7 ms	2132 KB	Output is correct
3	Correct	7 ms	2132 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 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	212 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	212 KB	Output is correct
16	Correct	7 ms	2136 KB	Output is correct
17	Correct	79 ms	17108 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	256 KB	Output is correct
20	Incorrect	1 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #579495

Compilation message