oj.uz

답안 #527096

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527096 2022-02-17T01:50:52 Z Leonardo_Paes 이상한 기계 (APIO19_strange_device) C++17
35 / 100
 678 ms 79228 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define f first
#define s second
// number x and x + (a / gcd(a, b+1) * b) are equal

ll gcd(ll a, ll b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

bool overflow(ll a, ll b){
	ll v = a*b;
	if(a == v/b) return true;
	return false;
}

const ll inf = 1e18;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n;
	ll a, b;
	cin >> n >> a >> b;
	ll aux = a / (gcd(a, b+1));
	bool ok = overflow(aux, b);	
	ll m = (ok ? aux * b : inf + 1);
	vector<pii> v;
	bool mx = 0;
	for(int i=0; i<n; i++){
		ll l, r;
		cin >> l >> r;
		if(r-l+1 >= m) mx = 1;
		l = l % m, r = r % m;
		if(l <= r){
			v.push_back({l, r});
			v.push_back({r, inf + 5});
		}
		else{
			v.push_back({l, m-1});
			v.push_back({m-1, inf + 5});
			v.push_back({0, r});
			v.push_back({r, inf + 5});
		}
	}
	if(mx){
		cout << m << "\n";
		return 0;
	}
	multiset<ll> s;
	ll ans = 0;
	sort(v.begin(), v.end());
	for(pii x : v){
		ll l = x.f, r = x.s;
		if(r == inf + 5){ // out
			s.erase(s.find(-l));
		}
		else{ // in
			if(s.empty()) ans += r-l+1;
			else{
				ll mxx = -(*s.begin());
				ans += max(0LL, r-mxx);
			}
			s.insert(-r);
		}
	}
	cout << ans << "\n";
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 6 ms 1232 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 6 ms 1232 KB Output is correct
17 Correct 67 ms 7136 KB Output is correct
18 Incorrect 1 ms 208 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 678 ms 79228 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 528 ms 34476 KB Output is correct
3 Correct 562 ms 34476 KB Output is correct
4 Correct 517 ms 34340 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 528 ms 34476 KB Output is correct
3 Correct 562 ms 34476 KB Output is correct
4 Correct 517 ms 34340 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 531 ms 34492 KB Output is correct
7 Correct 518 ms 34368 KB Output is correct
8 Correct 520 ms 34364 KB Output is correct
9 Correct 582 ms 34496 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 528 ms 34476 KB Output is correct
3 Correct 562 ms 34476 KB Output is correct
4 Correct 517 ms 34340 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 51 ms 6852 KB Output is correct
7 Correct 53 ms 7004 KB Output is correct
8 Correct 50 ms 6612 KB Output is correct
9 Correct 50 ms 6460 KB Output is correct
10 Correct 48 ms 6212 KB Output is correct
11 Correct 50 ms 5812 KB Output is correct
12 Correct 48 ms 5368 KB Output is correct
13 Correct 53 ms 5436 KB Output is correct
14 Correct 49 ms 5376 KB Output is correct
15 Correct 56 ms 5460 KB Output is correct
16 Correct 54 ms 5472 KB Output is correct
17 Correct 49 ms 5392 KB Output is correct
18 Correct 514 ms 34224 KB Output is correct
19 Correct 490 ms 34208 KB Output is correct
20 Correct 588 ms 34196 KB Output is correct
21 Correct 56 ms 5428 KB Output is correct
22 Correct 44 ms 5420 KB Output is correct
23 Correct 223 ms 27804 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 57 ms 5452 KB Output is correct
3 Correct 53 ms 5428 KB Output is correct
4 Correct 610 ms 34196 KB Output is correct
5 Correct 54 ms 5376 KB Output is correct
6 Correct 54 ms 5380 KB Output is correct
7 Correct 52 ms 5428 KB Output is correct
8 Correct 54 ms 5436 KB Output is correct
9 Correct 53 ms 5436 KB Output is correct
10 Correct 55 ms 5360 KB Output is correct
11 Correct 58 ms 5352 KB Output is correct
12 Correct 48 ms 5436 KB Output is correct
13 Correct 56 ms 5436 KB Output is correct
14 Correct 576 ms 34304 KB Output is correct
15 Correct 56 ms 5356 KB Output is correct
16 Correct 472 ms 34252 KB Output is correct
17 Correct 511 ms 34064 KB Output is correct
18 Incorrect 0 ms 204 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 6 ms 1232 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 6 ms 1232 KB Output is correct
17 Correct 67 ms 7136 KB Output is correct
18 Incorrect 1 ms 208 KB Output isn't correct
19 Halted 0 ms 0 KB -