oj.uz

Submission #333138

# Submission time Handle Problem Language Result Execution time Memory
333138 2020-12-04T18:22:42 Z qwe854896 Strange Device (APIO19_strange_device) C++14
65 / 100
 842 ms 82256 KB 
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define X first
#define Y second
using namespace std;

map <int, int> m;

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, A, B;
	cin >> n >> A >> B;
	int ans = 0, MOD = log10(A) - log10(__gcd(A, B+1)) + log10(B) > 18 ? (long long)(1e18+1) : A / __gcd(A, B+1) * B;
	while (n--) {
		int l, r;
		cin >> l >> r;
		int L = l % MOD, R = r % MOD;
		if (L < R) m[L]++, m[R+1]--;
		else if (L > R) m[L]++, m[MOD]--, m[0]++, m[R+1]--;
		else if (l == r) m[L]++, m[L+1]--;
		else ans = MOD;
	}
	int sum = 0, f = 1, l;
	if (ans != MOD) {
		for (auto seg:m) {
			//cout << seg.X << ' ' << seg.Y << endl;
			sum += seg.Y;
			if (sum and f) l = seg.X, f = 0;
			else if (!sum) ans += seg.X - l, f = 1;
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:32:32: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |    else if (!sum) ans += seg.X - l, f = 1;
      |                          ~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 10 ms 1388 KB Output is correct
3 Correct 8 ms 1388 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 1388 KB Output is correct
17 Correct 74 ms 10348 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 315 ms 21244 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 796 ms 82256 KB Output is correct
3 Correct 771 ms 73588 KB Output is correct
4 Correct 803 ms 73592 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 796 ms 82256 KB Output is correct
3 Correct 771 ms 73588 KB Output is correct
4 Correct 803 ms 73592 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 762 ms 73460 KB Output is correct
7 Correct 796 ms 73332 KB Output is correct
8 Correct 754 ms 73580 KB Output is correct
9 Correct 806 ms 73572 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 796 ms 82256 KB Output is correct
3 Correct 771 ms 73588 KB Output is correct
4 Correct 803 ms 73592 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 68 ms 10348 KB Output is correct
7 Correct 76 ms 10476 KB Output is correct
8 Correct 68 ms 10348 KB Output is correct
9 Correct 74 ms 10348 KB Output is correct
10 Correct 69 ms 10348 KB Output is correct
11 Correct 67 ms 10348 KB Output is correct
12 Correct 72 ms 10348 KB Output is correct
13 Correct 74 ms 10348 KB Output is correct
14 Correct 73 ms 10348 KB Output is correct
15 Correct 77 ms 10348 KB Output is correct
16 Correct 75 ms 10348 KB Output is correct
17 Correct 89 ms 10496 KB Output is correct
18 Correct 757 ms 73324 KB Output is correct
19 Correct 794 ms 72428 KB Output is correct
20 Correct 832 ms 73100 KB Output is correct
21 Correct 69 ms 10348 KB Output is correct
22 Correct 81 ms 10348 KB Output is correct
23 Correct 127 ms 13036 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 81 ms 10476 KB Output is correct
3 Correct 75 ms 10348 KB Output is correct
4 Correct 842 ms 82160 KB Output is correct
5 Correct 77 ms 10348 KB Output is correct
6 Correct 78 ms 10348 KB Output is correct
7 Correct 76 ms 10348 KB Output is correct
8 Correct 75 ms 10348 KB Output is correct
9 Correct 74 ms 10348 KB Output is correct
10 Correct 82 ms 10416 KB Output is correct
11 Correct 77 ms 10348 KB Output is correct
12 Correct 77 ms 10348 KB Output is correct
13 Correct 75 ms 10348 KB Output is correct
14 Correct 824 ms 73884 KB Output is correct
15 Correct 67 ms 10348 KB Output is correct
16 Correct 737 ms 73108 KB Output is correct
17 Correct 747 ms 72684 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 10 ms 1388 KB Output is correct
3 Correct 8 ms 1388 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 1388 KB Output is correct
17 Correct 74 ms 10348 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -