oj.uz

Submission #316827

# Submission time Handle Problem Language Result Execution time Memory
316827 2020-10-28T09:14:26 Z sofapuden Strange Device (APIO19_strange_device) C++14
10 / 100
 3224 ms 25344 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
	ll n, a, b; cin >> n >> a >> b;
	ll ans = 0;
	if(LONG_LONG_MAX/b <= a){
		for(int i = 0; i < n; ++i){
			ll l, r; cin >> l >> r;
			ans+=r-l+1ll;
		}
		cout << ans << "\n";
		return 0;	
	}
	vector<array<ll,3>> inter;
	for(int i = 0; i < n; ++i){
		ll l, r; cin >> l >> r;
		if((r/(a*b))-(l/(a*b)) >= 2 || ((r/(a*b))-(l/(a*b)) >= 1 && (r%(a*b)) >= (l%(a*b)))){
			cout << a*b << "\n";
			return 0;
		}
		if((r/(a*b))-(l/(a*b)) >= 1){
			inter.push_back({0,l%(a*b),r%(a*b)});
		}
		else{
			inter.push_back({1,l%(a*b),r%(a*b)});
		}
	}
	sort(inter.begin(),inter.end());
	pair<ll,ll> hi= {1ll,inter[0][2]};
	if(inter[0][0] == 1){
		ans = inter[0][1];
	}
	for(int i = 0; i < n; ++i){
		if(inter[i][0] && !inter[0][0] && inter[i][1] >= inter[0][1])break;
		if(inter[i][0] && inter[i][1] > hi.second+1){
			ans += inter[i][1] - hi.second -1;
		}
		hi = max(hi,make_pair(1ll,inter[i][2]));
	}
	if(inter[0][0] == 1){
		ans+=a*b-hi.second-1;
	}
	else{
		ans+=max(0ll,inter[0][1]-hi.second-1);
	}
		
	cout << a*b - ans << "\n";
}

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2202 ms 25032 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3173 ms 25344 KB Output is correct
3 Incorrect 3167 ms 25332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3173 ms 25344 KB Output is correct
3 Incorrect 3167 ms 25332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 3173 ms 25344 KB Output is correct
3 Incorrect 3167 ms 25332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 321 ms 3692 KB Output is correct
3 Correct 335 ms 3564 KB Output is correct
4 Correct 3224 ms 25344 KB Output is correct
5 Correct 316 ms 3560 KB Output is correct
6 Correct 317 ms 3688 KB Output is correct
7 Correct 314 ms 3560 KB Output is correct
8 Correct 317 ms 3560 KB Output is correct
9 Correct 315 ms 3504 KB Output is correct
10 Correct 314 ms 3560 KB Output is correct
11 Correct 317 ms 3692 KB Output is correct
12 Correct 305 ms 3560 KB Output is correct
13 Correct 320 ms 3488 KB Output is correct
14 Correct 3177 ms 25280 KB Output is correct
15 Incorrect 317 ms 3620 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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