oj.uz

Submission #410633

# Submission time Handle Problem Language Result Execution time Memory
410633 2021-05-23T08:03:46 Z dynam1c Strange Device (APIO19_strange_device) C++17
0 / 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;
	vector<bool> vis(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++)
			vis[t%(a*b)] = true;
	}
	for (ll t = 0; t < a*b; t++) if (vis[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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 58 ms 13156 KB Output is correct
3 Correct 71 ms 18484 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 2 ms 332 KB Output is correct
9 Correct 5 ms 1100 KB Output is correct
10 Correct 1 ms 204 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 332 KB Output is correct
15 Correct 31 ms 7020 KB Output is correct
16 Correct 31 ms 6732 KB Output is correct
17 Correct 64 ms 6736 KB Output is correct
18 Runtime error 4 ms 460 KB Execution killed with signal 6

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 5027 ms 15308 KB Time limit exceeded
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 146 ms 32284 KB Output is correct
3 Correct 195 ms 32196 KB Output is correct
4 Correct 149 ms 30620 KB Output is correct
5 Execution timed out 5060 ms 424 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 652 ms 63064 KB Output is correct
3 Runtime error 246 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 652 ms 63064 KB Output is correct
3 Runtime error 246 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 652 ms 63064 KB Output is correct
3 Runtime error 246 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 2225 ms 524288 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 58 ms 13156 KB Output is correct
3 Correct 71 ms 18484 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 2 ms 332 KB Output is correct
9 Correct 5 ms 1100 KB Output is correct
10 Correct 1 ms 204 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 332 KB Output is correct
15 Correct 31 ms 7020 KB Output is correct
16 Correct 31 ms 6732 KB Output is correct
17 Correct 64 ms 6736 KB Output is correct
18 Runtime error 4 ms 460 KB Execution killed with signal 6