답안 #572365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572365	2022-06-04T09:53:48 Z	CpDark	이상한 기계 (APIO19_strange_device)	C++14	65 / 100	520 ms	32740 KB

strange_device

#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 + 1;
	else {
		if (mod > LLONG_MAX / B)mod = 1e18 + 1;
		else mod *= B;
	}
	if (mod < 0)mod = 1e18 + 1;
	vp times(n);
	vp points;
	ll l, r;
	for (int i = 0; i < n; i++) {
		cin >> l >> r;
		times[i] = { l,r};
		if (l - r + 1 >= mod) {
			cout << mod;
			return 0;
		}
		pushTime(times[i], mod, points);
	}
	
	sort(points.begin(), points.end());
	ll count = 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:73: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]
   73 |  for (int i = 1; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	6 ms	852 KB	Output is correct
3	Correct	4 ms	852 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 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	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	6 ms	852 KB	Output is correct
17	Correct	46 ms	4048 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	402 ms	32528 KB	Output is correct
3	Correct	401 ms	32596 KB	Output is correct
4	Correct	379 ms	32536 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	402 ms	32528 KB	Output is correct
3	Correct	401 ms	32596 KB	Output is correct
4	Correct	379 ms	32536 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	407 ms	32544 KB	Output is correct
7	Correct	415 ms	32404 KB	Output is correct
8	Correct	449 ms	32428 KB	Output is correct
9	Correct	454 ms	32448 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	402 ms	32528 KB	Output is correct
3	Correct	401 ms	32596 KB	Output is correct
4	Correct	379 ms	32536 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	40 ms	4048 KB	Output is correct
7	Correct	63 ms	3996 KB	Output is correct
8	Correct	39 ms	4052 KB	Output is correct
9	Correct	44 ms	4100 KB	Output is correct
10	Correct	57 ms	4224 KB	Output is correct
11	Correct	56 ms	4212 KB	Output is correct
12	Correct	38 ms	4292 KB	Output is correct
13	Correct	40 ms	4204 KB	Output is correct
14	Correct	39 ms	4312 KB	Output is correct
15	Correct	43 ms	4300 KB	Output is correct
16	Correct	52 ms	4240 KB	Output is correct
17	Correct	53 ms	4168 KB	Output is correct
18	Correct	469 ms	32740 KB	Output is correct
19	Correct	428 ms	32716 KB	Output is correct
20	Correct	507 ms	32700 KB	Output is correct
21	Correct	48 ms	4224 KB	Output is correct
22	Correct	41 ms	4244 KB	Output is correct
23	Correct	137 ms	14388 KB	Output is correct

Subtask #7
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	58 ms	4192 KB	Output is correct
3	Correct	54 ms	4300 KB	Output is correct
4	Correct	520 ms	32712 KB	Output is correct
5	Correct	49 ms	4252 KB	Output is correct
6	Correct	46 ms	4132 KB	Output is correct
7	Correct	44 ms	4256 KB	Output is correct
8	Correct	47 ms	4256 KB	Output is correct
9	Correct	55 ms	4188 KB	Output is correct
10	Correct	54 ms	4160 KB	Output is correct
11	Correct	52 ms	4132 KB	Output is correct
12	Correct	54 ms	4240 KB	Output is correct
13	Correct	57 ms	4304 KB	Output is correct
14	Correct	454 ms	32708 KB	Output is correct
15	Correct	59 ms	4208 KB	Output is correct
16	Correct	473 ms	32708 KB	Output is correct
17	Correct	437 ms	32716 KB	Output is correct
18	Correct	1 ms	224 KB	Output is correct

Subtask #8
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	6 ms	852 KB	Output is correct
3	Correct	4 ms	852 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 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	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	6 ms	852 KB	Output is correct
17	Correct	46 ms	4048 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Incorrect	0 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-