Submission #132359

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
132359	2019-07-18T18:22:25 Z	bogdan10bos	Strange Device (APIO19_strange_device)	C++14	35 / 100	2806 ms	18192 KB

strange_device

/// Just for others, not for me :( 9 days and counting
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> pii;

LL A, B;

int main()
{
	//freopen("1.in", "r", stdin);

	int T;
	cin >> T >> A >> B;

	LL d = __gcd(A, B + 1);
	LL K = A / d;
	K *= B;

	vector<pii> itvs;
	for(int i = 1; i <= T; i++)
	{
		LL st, dr;
		cin >> st >> dr;
		if(dr - st + 1 >= K)
		{
			cout << K << '\n';
			exit(0);
		}
		st %= K, dr %= K;
		if(st <= dr)
			itvs.push_back({st, dr});
		else
		{
			itvs.push_back({st, K - 1});
			itvs.push_back({0, dr});
		}
	}

	sort(itvs.begin(), itvs.end(),
		[](pii a, pii b)
		{
			if(a.second == b.second)	return a.first < b.first;
			return a.second < b.second;
		});

	LL ans = 0;
	while(!itvs.empty())
	{
		pii itv = itvs.back();
		itvs.pop_back();
		while(!itvs.empty())
		{
			if(itvs.back().second >= itv.first)
			{
				pii itv2 = itvs.back();
				itvs.pop_back();
				itv.first = min(itv.first, itv2.first);
			}
			else
				break;
		}

		ans += itv.second - itv.first + 1;
	}

	cout << ans << '\n';
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	29 ms	988 KB	Output is correct
3	Correct	29 ms	1144 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	3 ms	256 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct
13	Correct	2 ms	256 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	29 ms	1116 KB	Output is correct
17	Correct	277 ms	4328 KB	Output is correct
18	Incorrect	2 ms	256 KB	Output isn't correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Incorrect	3 ms	376 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	5 ms	504 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	1887 ms	17892 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2700 ms	17396 KB	Output is correct
3	Correct	2654 ms	17332 KB	Output is correct
4	Correct	2659 ms	17080 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2700 ms	17396 KB	Output is correct
3	Correct	2654 ms	17332 KB	Output is correct
4	Correct	2659 ms	17080 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2664 ms	16860 KB	Output is correct
7	Correct	2695 ms	17072 KB	Output is correct
8	Correct	2675 ms	17004 KB	Output is correct
9	Correct	2776 ms	17188 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2700 ms	17396 KB	Output is correct
3	Correct	2654 ms	17332 KB	Output is correct
4	Correct	2659 ms	17080 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	266 ms	3180 KB	Output is correct
7	Correct	272 ms	2920 KB	Output is correct
8	Correct	282 ms	3020 KB	Output is correct
9	Correct	270 ms	2840 KB	Output is correct
10	Correct	268 ms	2888 KB	Output is correct
11	Correct	277 ms	2892 KB	Output is correct
12	Correct	268 ms	2924 KB	Output is correct
13	Correct	277 ms	2924 KB	Output is correct
14	Correct	266 ms	2944 KB	Output is correct
15	Correct	273 ms	2812 KB	Output is correct
16	Correct	273 ms	3948 KB	Output is correct
17	Correct	272 ms	3884 KB	Output is correct
18	Correct	2667 ms	18084 KB	Output is correct
19	Correct	2652 ms	18080 KB	Output is correct
20	Correct	2772 ms	18192 KB	Output is correct
21	Correct	273 ms	3916 KB	Output is correct
22	Correct	267 ms	4120 KB	Output is correct
23	Correct	975 ms	11372 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	273 ms	2692 KB	Output is correct
3	Correct	274 ms	3432 KB	Output is correct
4	Correct	2806 ms	17564 KB	Output is correct
5	Correct	285 ms	3628 KB	Output is correct
6	Correct	277 ms	3600 KB	Output is correct
7	Correct	274 ms	3696 KB	Output is correct
8	Correct	275 ms	3772 KB	Output is correct
9	Correct	272 ms	3816 KB	Output is correct
10	Correct	271 ms	3408 KB	Output is correct
11	Correct	275 ms	3344 KB	Output is correct
12	Correct	264 ms	3396 KB	Output is correct
13	Correct	274 ms	3436 KB	Output is correct
14	Correct	2790 ms	17344 KB	Output is correct
15	Correct	271 ms	4104 KB	Output is correct
16	Correct	2673 ms	18088 KB	Output is correct
17	Correct	2672 ms	18164 KB	Output is correct
18	Incorrect	2 ms	256 KB	Output isn't correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	29 ms	988 KB	Output is correct
3	Correct	29 ms	1144 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	3 ms	256 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct
13	Correct	2 ms	256 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	29 ms	1116 KB	Output is correct
17	Correct	277 ms	4328 KB	Output is correct
18	Incorrect	2 ms	256 KB	Output isn't correct

Submission #132359

Compilation message