oj.uz

Submission #132355

# Submission time Handle Problem Language Result Execution time Memory
132355 2019-07-18T18:13:23 Z bogdan10bos Strange Device (APIO19_strange_device) C++14
10 / 100
 2752 ms 19060 KB 
/// 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());

	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 348 KB Output is correct
2 Incorrect 29 ms 1020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2654 ms 19060 KB Output is correct
3 Correct 2658 ms 17808 KB Output is correct
4 Correct 2642 ms 17840 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2654 ms 19060 KB Output is correct
3 Correct 2658 ms 17808 KB Output is correct
4 Correct 2642 ms 17840 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2640 ms 17924 KB Output is correct
7 Correct 2693 ms 18024 KB Output is correct
8 Correct 2625 ms 18040 KB Output is correct
9 Correct 2692 ms 17924 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2654 ms 19060 KB Output is correct
3 Correct 2658 ms 17808 KB Output is correct
4 Correct 2642 ms 17840 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 332 ms 3644 KB Output is correct
7 Correct 272 ms 3744 KB Output is correct
8 Correct 267 ms 3764 KB Output is correct
9 Correct 267 ms 3828 KB Output is correct
10 Correct 264 ms 3764 KB Output is correct
11 Correct 269 ms 3840 KB Output is correct
12 Correct 269 ms 3808 KB Output is correct
13 Correct 302 ms 3788 KB Output is correct
14 Correct 327 ms 3940 KB Output is correct
15 Incorrect 273 ms 3692 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 276 ms 3880 KB Output is correct
3 Correct 276 ms 3660 KB Output is correct
4 Correct 2752 ms 17768 KB Output is correct
5 Correct 274 ms 3600 KB Output is correct
6 Correct 277 ms 3696 KB Output is correct
7 Correct 272 ms 3816 KB Output is correct
8 Correct 271 ms 3756 KB Output is correct
9 Correct 271 ms 3700 KB Output is correct
10 Correct 271 ms 3844 KB Output is correct
11 Correct 294 ms 3824 KB Output is correct
12 Correct 265 ms 3788 KB Output is correct
13 Correct 276 ms 3832 KB Output is correct
14 Incorrect 2715 ms 17944 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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