oj.uz

Submission #198262

# Submission time Handle Problem Language Result Execution time Memory
198262 2020-01-25T09:11:19 Z AMO5 Strange Device (APIO19_strange_device) C++
0 / 100
 5000 ms 524292 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < ll ,ll> pll; 

ll n,a,b;
map < pll , ll >vis;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> a >> b;
	ll le,ri, ans = 0;
	bool all = 0;
	if(n==1){
		cin >> le >> ri;
		if(ri-le+1>=a*b){
			ans = a*b;
		}else{
			le %= (a*b);
			ri %= (a*b);
			ans = abs(ri-le+1);
			if(le>ri){
				ans = a*b-ans;
			}
		}
		cout << ans << endl;
		return 0;
	}
	for(ll i = 0; i < n; i++){
		cin >> le >> ri;
		if(ri-le+1>=a*b){
			all = 1;
		}
		for(ll j = le; j <= ri&&!all; j++){
			ll t = j;
			ll x = (t+(t/b))%a;
			ll y = t%b;
			if(!vis[{x,y}]){
				ans++;
			}
			vis[{x,y}]++;
		}
	}
	if(all)ans=a*b;
	cout << ans << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 97 ms 12664 KB Output is correct
3 Correct 175 ms 18304 KB Output is correct
4 Correct 5 ms 888 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 248 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 17 ms 1272 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 92 ms 7032 KB Output is correct
16 Correct 57 ms 7160 KB Output is correct
17 Correct 109 ms 10360 KB Output is correct
18 Incorrect 2 ms 384 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 352 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 376 KB Output is correct
2 Correct 278 ms 32348 KB Output is correct
3 Correct 303 ms 32120 KB Output is correct
4 Correct 278 ms 30712 KB Output is correct
5 Execution timed out 5075 ms 62620 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 961 ms 69552 KB Output is correct
3 Runtime error 4949 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 961 ms 69552 KB Output is correct
3 Runtime error 4949 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 961 ms 69552 KB Output is correct
3 Runtime error 4949 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3211 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 97 ms 12664 KB Output is correct
3 Correct 175 ms 18304 KB Output is correct
4 Correct 5 ms 888 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 248 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 17 ms 1272 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 92 ms 7032 KB Output is correct
16 Correct 57 ms 7160 KB Output is correct
17 Correct 109 ms 10360 KB Output is correct
18 Incorrect 2 ms 384 KB Output isn't correct