oj.uz

답안 #572361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572361 2022-06-04T09:46:06 Z CpDark 이상한 기계 (APIO19_strange_device) C++14
65 / 100
 474 ms 33464 KB 
#include <bits/stdc++.h>
#define fastInput ios::sync_with_stdio(false); cin.tie(nullptr);

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pii;
typedef vector<pii> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;

ll A, B;
inline pii getTime(ll t) {
	ll x = (t + (t / B)) % A;
	ll y = t % B;
	return { x,y };
}

inline void pushTime(pii p, ll mod, vp &points) {

	if (p.first % mod <= p.second % mod) {
		points.push_back({ p.first % mod, p.second % mod });
	}
	else {
		points.push_back({ p.first % mod, mod - 1 });
		points.push_back({ 0, p.second % mod });
	}
	
}

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


int main() {
	fastInput;
	int n;
	cin >> n >> A >> B;

	ll mod = (A / gcd(A, B + 1));
	if (mod < 0)mod = 1e18 + 7;
	mod *= B;
	if (mod < 0)mod = 1e18 + 7;
	vp times(n);
	vp points;
	ll l, r;
	for (int i = 0; i < n; i++) {
		cin >> l >> r;
		times[i] = { l,r};
		pushTime(times[i], mod, points);
	}
	
	sort(points.begin(), points.end());
	ll count = 0;
	int open = 0;
	ll last = points[0].second;
	ll start = points[0].first;
	for (int i = 1; i < points.size(); i++) {
		if (points[i].first > last) {
			ll amount = last - start + 1;
			start = points[i].first;
			count += amount;
		}
		last = max(last, points[i].second);
		
	}
	ll amount = last - start + 1;
	count += amount;
	cout << count;

	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (int i = 1; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
strange_device.cpp:64:6: warning: unused variable 'open' [-Wunused-variable]
   64 |  int open = 0;
      |      ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 5 ms 1228 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 5 ms 1236 KB Output is correct
17 Correct 44 ms 4744 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 293 ms 33168 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 426 ms 33372 KB Output is correct
3 Correct 381 ms 33184 KB Output is correct
4 Correct 387 ms 33164 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 426 ms 33372 KB Output is correct
3 Correct 381 ms 33184 KB Output is correct
4 Correct 387 ms 33164 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 401 ms 33148 KB Output is correct
7 Correct 386 ms 33460 KB Output is correct
8 Correct 389 ms 33200 KB Output is correct
9 Correct 474 ms 33200 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 426 ms 33372 KB Output is correct
3 Correct 381 ms 33184 KB Output is correct
4 Correct 387 ms 33164 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 40 ms 4720 KB Output is correct
7 Correct 44 ms 4832 KB Output is correct
8 Correct 39 ms 4680 KB Output is correct
9 Correct 38 ms 4664 KB Output is correct
10 Correct 38 ms 4688 KB Output is correct
11 Correct 38 ms 4692 KB Output is correct
12 Correct 42 ms 4668 KB Output is correct
13 Correct 53 ms 4700 KB Output is correct
14 Correct 39 ms 4724 KB Output is correct
15 Correct 45 ms 4680 KB Output is correct
16 Correct 40 ms 4464 KB Output is correct
17 Correct 39 ms 4720 KB Output is correct
18 Correct 428 ms 33288 KB Output is correct
19 Correct 381 ms 33316 KB Output is correct
20 Correct 432 ms 33464 KB Output is correct
21 Correct 42 ms 4680 KB Output is correct
22 Correct 37 ms 4724 KB Output is correct
23 Correct 126 ms 15252 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 55 ms 4712 KB Output is correct
3 Correct 45 ms 4644 KB Output is correct
4 Correct 460 ms 33188 KB Output is correct
5 Correct 53 ms 4624 KB Output is correct
6 Correct 43 ms 4532 KB Output is correct
7 Correct 49 ms 4740 KB Output is correct
8 Correct 41 ms 4712 KB Output is correct
9 Correct 43 ms 4468 KB Output is correct
10 Correct 47 ms 4480 KB Output is correct
11 Correct 52 ms 4612 KB Output is correct
12 Correct 38 ms 4676 KB Output is correct
13 Correct 44 ms 4708 KB Output is correct
14 Correct 439 ms 33152 KB Output is correct
15 Correct 57 ms 4680 KB Output is correct
16 Correct 399 ms 33336 KB Output is correct
17 Correct 390 ms 32956 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 5 ms 1228 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 5 ms 1236 KB Output is correct
17 Correct 44 ms 4744 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 1 ms 320 KB Output isn't correct
21 Halted 0 ms 0 KB -