oj.uz

답안 #732050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
732050 2023-04-28T10:05:23 Z US3RN4M3 이상한 기계 (APIO19_strange_device) C++17
35 / 100
 1504 ms 49164 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, A, B;
vector<pair<ll, ll>> segs;
void solve2() {
	ll ans = 0;
	for(auto & [l, r] : segs) {
		cin >> l >> r;
		ans += r - l + 1;
	}
	cout << ans << endl;
}

ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}

//x(B+1) == 0
//x(b+1)
main() {
	cin >> n >> A >> B;
	segs.resize(n);
	assert(B <= 1e12);
	ll cycle = 1e18;
	ll C = A / (gcd(B + 1, A));
	if((B * C) / C == B) cycle = B * C;
	else {
		solve2();
		return 0;
	}
	if(cycle > 1e18 + 10) cycle = 1e18 + 10;
	vector<pair<ll, bool>> evt;
	for(auto & [l, r] : segs) {
		cin >> l >> r;
		r++;
		if(l >= cycle) {
			ll tmp = (l / cycle) * cycle;
			l -= tmp;
			r -= tmp;
		}
		if(r >= cycle*2) {
			cout << cycle << endl;
			return 0;
		}
		if(r >= cycle) {
			evt.push_back({l, true});
			evt.push_back({0, true});
			evt.push_back({r - cycle, false});
		} else {
			evt.push_back({l, true});
			evt.push_back({r, false});
		}
	}
	sort(evt.begin(), evt.end());
	ll prev = 0;
	int cnt = 0;
	ll ans = 0;
	for(auto [t, b] : evt) {
		ll delta = t - prev;
		prev = t;
		if(cnt > 0) ans += delta;
		if(b) cnt++;
		else cnt--;
	}
	if(cnt > 0) ans += cycle - prev;
	cout << ans << endl;
}

Compilation message

strange_device.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 16 ms 1104 KB Output is correct
3 Correct 14 ms 1104 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 240 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1000 KB Output is correct
17 Correct 146 ms 6080 KB Output is correct
18 Runtime error 1 ms 340 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 340 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 960 ms 48888 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1346 ms 49164 KB Output is correct
3 Correct 1354 ms 48880 KB Output is correct
4 Correct 1340 ms 49076 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1346 ms 49164 KB Output is correct
3 Correct 1354 ms 48880 KB Output is correct
4 Correct 1340 ms 49076 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1371 ms 48812 KB Output is correct
7 Correct 1357 ms 48788 KB Output is correct
8 Correct 1376 ms 48980 KB Output is correct
9 Correct 1464 ms 48964 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1346 ms 49164 KB Output is correct
3 Correct 1354 ms 48880 KB Output is correct
4 Correct 1340 ms 49076 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 137 ms 6104 KB Output is correct
7 Correct 138 ms 6008 KB Output is correct
8 Correct 136 ms 5988 KB Output is correct
9 Correct 137 ms 6016 KB Output is correct
10 Correct 133 ms 6088 KB Output is correct
11 Correct 139 ms 6080 KB Output is correct
12 Correct 141 ms 6092 KB Output is correct
13 Correct 145 ms 6084 KB Output is correct
14 Correct 140 ms 6076 KB Output is correct
15 Correct 141 ms 5984 KB Output is correct
16 Correct 149 ms 6092 KB Output is correct
17 Correct 144 ms 6076 KB Output is correct
18 Correct 1357 ms 48972 KB Output is correct
19 Correct 1366 ms 49048 KB Output is correct
20 Correct 1468 ms 49012 KB Output is correct
21 Correct 145 ms 6084 KB Output is correct
22 Correct 135 ms 6036 KB Output is correct
23 Correct 427 ms 22184 KB Output is correct

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 144 ms 5976 KB Output is correct
3 Correct 141 ms 6036 KB Output is correct
4 Correct 1504 ms 48880 KB Output is correct
5 Correct 140 ms 5980 KB Output is correct
6 Correct 145 ms 6124 KB Output is correct
7 Correct 138 ms 6052 KB Output is correct
8 Correct 141 ms 6076 KB Output is correct
9 Correct 140 ms 6084 KB Output is correct
10 Correct 142 ms 6076 KB Output is correct
11 Correct 140 ms 6024 KB Output is correct
12 Runtime error 3 ms 3540 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 16 ms 1104 KB Output is correct
3 Correct 14 ms 1104 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 240 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 14 ms 1000 KB Output is correct
17 Correct 146 ms 6080 KB Output is correct
18 Runtime error 1 ms 340 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -