oj.uz

Submission #316826

# Submission time Handle Problem Language Result Execution time Memory
316826 2020-10-28T09:09:14 Z sofapuden Strange Device (APIO19_strange_device) C++14
10 / 100
 3214 ms 28884 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[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 1216 KB Output is correct
3 Correct 33 ms 1472 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 1 ms 256 KB Output is correct
2 Correct 0 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 1 ms 256 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 4 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 2235 ms 28068 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3141 ms 28872 KB Output is correct
3 Incorrect 3168 ms 28884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3141 ms 28872 KB Output is correct
3 Incorrect 3168 ms 28884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3141 ms 28872 KB Output is correct
3 Incorrect 3168 ms 28884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 320 ms 6316 KB Output is correct
3 Correct 318 ms 6368 KB Output is correct
4 Correct 3214 ms 27924 KB Output is correct
5 Correct 321 ms 6224 KB Output is correct
6 Correct 318 ms 6252 KB Output is correct
7 Correct 321 ms 6404 KB Output is correct
8 Correct 329 ms 6268 KB Output is correct
9 Correct 327 ms 6256 KB Output is correct
10 Correct 314 ms 6252 KB Output is correct
11 Correct 323 ms 6248 KB Output is correct
12 Correct 316 ms 6248 KB Output is correct
13 Correct 320 ms 6236 KB Output is correct
14 Correct 3213 ms 27536 KB Output is correct
15 Incorrect 324 ms 6252 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 1216 KB Output is correct
3 Correct 33 ms 1472 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -