oj.uz

Submission #572348

# Submission time Handle Problem Language Result Execution time Memory
572348 2022-06-04T09:38:33 Z CpDark Strange Device (APIO19_strange_device) C++14
65 / 100
 568 ms 68924 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 * B / gcd(A, B + 1);
	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:65: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]
   65 |  for (int i = 1; i < points.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
strange_device.cpp:62:6: warning: unused variable 'open' [-Wunused-variable]
   62 |  int open = 0;
      |      ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 1240 KB Output is correct
3 Correct 8 ms 1252 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 7 ms 1224 KB Output is correct
17 Correct 58 ms 7208 KB Output is correct
18 Correct 1 ms 320 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 374 ms 57112 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 496 ms 52276 KB Output is correct
3 Correct 568 ms 68916 KB Output is correct
4 Correct 483 ms 68924 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 496 ms 52276 KB Output is correct
3 Correct 568 ms 68916 KB Output is correct
4 Correct 483 ms 68924 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 477 ms 68808 KB Output is correct
7 Correct 489 ms 68560 KB Output is correct
8 Correct 509 ms 68720 KB Output is correct
9 Correct 508 ms 68792 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 496 ms 52276 KB Output is correct
3 Correct 568 ms 68916 KB Output is correct
4 Correct 483 ms 68924 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 48 ms 7240 KB Output is correct
7 Correct 63 ms 7248 KB Output is correct
8 Correct 57 ms 7232 KB Output is correct
9 Correct 51 ms 7284 KB Output is correct
10 Correct 48 ms 7200 KB Output is correct
11 Correct 54 ms 7320 KB Output is correct
12 Correct 60 ms 7224 KB Output is correct
13 Correct 70 ms 7268 KB Output is correct
14 Correct 50 ms 7208 KB Output is correct
15 Correct 46 ms 7280 KB Output is correct
16 Correct 45 ms 7292 KB Output is correct
17 Correct 43 ms 7216 KB Output is correct
18 Correct 532 ms 68660 KB Output is correct
19 Correct 496 ms 68600 KB Output is correct
20 Correct 529 ms 68468 KB Output is correct
21 Correct 62 ms 7304 KB Output is correct
22 Correct 49 ms 7228 KB Output is correct
23 Correct 165 ms 23856 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 46 ms 7184 KB Output is correct
3 Correct 46 ms 7304 KB Output is correct
4 Correct 561 ms 68616 KB Output is correct
5 Correct 62 ms 7188 KB Output is correct
6 Correct 73 ms 7240 KB Output is correct
7 Correct 42 ms 7244 KB Output is correct
8 Correct 50 ms 7300 KB Output is correct
9 Correct 46 ms 7272 KB Output is correct
10 Correct 50 ms 7256 KB Output is correct
11 Correct 55 ms 7224 KB Output is correct
12 Correct 60 ms 7280 KB Output is correct
13 Correct 48 ms 7300 KB Output is correct
14 Correct 532 ms 68900 KB Output is correct
15 Correct 49 ms 7228 KB Output is correct
16 Correct 411 ms 68900 KB Output is correct
17 Correct 455 ms 68756 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 1240 KB Output is correct
3 Correct 8 ms 1252 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 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 320 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 7 ms 1224 KB Output is correct
17 Correct 58 ms 7208 KB Output is correct
18 Correct 1 ms 320 KB Output is correct
19 Correct 1 ms 320 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -