oj.uz

Submission #410632

# Submission time Handle Problem Language Result Execution time Memory
410632 2021-05-23T08:00:02 Z dynam1c Strange Device (APIO19_strange_device) C++17
10 / 100
 5000 ms 524292 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	ll n, a, b;
	cin >> n >> a >> b;
	set<pair<ll, ll>> s;
	for (int i = 0; i < n; i++) {
		ll l, r;
		cin >> l >> r;
		for (ll t = l; t <= r; t++)
			s.emplace((t+t/b) % a, t % b);
	}
	cout << s.size() << endl;
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 12720 KB Output is correct
3 Correct 74 ms 18176 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 9 ms 1100 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 44 ms 6988 KB Output is correct
16 Correct 29 ms 7116 KB Output is correct
17 Correct 68 ms 10304 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 2547 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 149 ms 32228 KB Output is correct
3 Correct 212 ms 32032 KB Output is correct
4 Correct 129 ms 30620 KB Output is correct
5 Execution timed out 5093 ms 62516 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 627 ms 65428 KB Output is correct
3 Runtime error 2154 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 627 ms 65428 KB Output is correct
3 Runtime error 2154 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 627 ms 65428 KB Output is correct
3 Runtime error 2154 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1851 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 12720 KB Output is correct
3 Correct 74 ms 18176 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 9 ms 1100 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 44 ms 6988 KB Output is correct
16 Correct 29 ms 7116 KB Output is correct
17 Correct 68 ms 10304 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Runtime error 2547 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -