Submission #579492

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579492	2022-06-19T09:06:27 Z	gun_gan	Strange Device (APIO19_strange_device)	C++17	65 / 100	921 ms	163728 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 = 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	260 KB	Output is correct
2	Correct	9 ms	2036 KB	Output is correct
3	Correct	8 ms	2132 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 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	320 KB	Output is correct
13	Correct	1 ms	324 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	2132 KB	Output is correct
17	Correct	76 ms	17128 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	584 ms	80256 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	751 ms	163572 KB	Output is correct
3	Correct	774 ms	163560 KB	Output is correct
4	Correct	778 ms	163704 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	751 ms	163572 KB	Output is correct
3	Correct	774 ms	163560 KB	Output is correct
4	Correct	778 ms	163704 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	791 ms	163728 KB	Output is correct
7	Correct	755 ms	163624 KB	Output is correct
8	Correct	809 ms	163620 KB	Output is correct
9	Correct	837 ms	163612 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	751 ms	163572 KB	Output is correct
3	Correct	774 ms	163560 KB	Output is correct
4	Correct	778 ms	163704 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	73 ms	17068 KB	Output is correct
7	Correct	68 ms	17060 KB	Output is correct
8	Correct	86 ms	17072 KB	Output is correct
9	Correct	101 ms	17144 KB	Output is correct
10	Correct	67 ms	17096 KB	Output is correct
11	Correct	70 ms	17120 KB	Output is correct
12	Correct	69 ms	17080 KB	Output is correct
13	Correct	81 ms	17104 KB	Output is correct
14	Correct	83 ms	17148 KB	Output is correct
15	Correct	86 ms	17096 KB	Output is correct
16	Correct	70 ms	17092 KB	Output is correct
17	Correct	67 ms	17100 KB	Output is correct
18	Correct	761 ms	163516 KB	Output is correct
19	Correct	785 ms	163504 KB	Output is correct
20	Correct	775 ms	163628 KB	Output is correct
21	Correct	81 ms	17140 KB	Output is correct
22	Correct	74 ms	17072 KB	Output is correct
23	Correct	228 ms	31560 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	85 ms	17112 KB	Output is correct
3	Correct	81 ms	17144 KB	Output is correct
4	Correct	921 ms	163576 KB	Output is correct
5	Correct	75 ms	17132 KB	Output is correct
6	Correct	73 ms	17144 KB	Output is correct
7	Correct	78 ms	17120 KB	Output is correct
8	Correct	96 ms	17080 KB	Output is correct
9	Correct	85 ms	17076 KB	Output is correct
10	Correct	70 ms	17188 KB	Output is correct
11	Correct	73 ms	17072 KB	Output is correct
12	Correct	68 ms	17180 KB	Output is correct
13	Correct	76 ms	17088 KB	Output is correct
14	Correct	819 ms	163544 KB	Output is correct
15	Correct	77 ms	17088 KB	Output is correct
16	Correct	732 ms	163524 KB	Output is correct
17	Correct	743 ms	163596 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	260 KB	Output is correct
2	Correct	9 ms	2036 KB	Output is correct
3	Correct	8 ms	2132 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 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	320 KB	Output is correct
13	Correct	1 ms	324 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	2132 KB	Output is correct
17	Correct	76 ms	17128 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Incorrect	0 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #579492

Compilation message