oj.uz

Submission #320985

# Submission time Handle Problem Language Result Execution time Memory
320985 2020-11-10T12:35:50 Z Drew_ Strange Device (APIO19_strange_device) C++14
30 / 100
 752 ms 86452 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x...) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

ld const PI = 4*atan((ld)1);

int main()
{
	fastio;

	ll n, a, b;
	cin >> n >> a >> b;

	vector<pl> v(n);
	for (pl &x : v)
		cin >> x.f1 >> x.s2;

	if (v.back().s2/a < b)
	{
		ll res = 0;
		for (pl x : v)
			res += (x.s2 - x.f1 + 1);
		cout << res << '\n';
		return 0;
	}

	ll gcd = __gcd(a, b+1);
	ll mod =  (a/gcd) * b;

	
	vector<pl> range; //first: duration, second: state
	for (pl x : v)
	{
		if (x.s2 - x.f1 >= mod)
		{
			cout << mod << '\n';
			return 0;
		}

		ll l = x.f1 % mod;
		ll r = x.s2 % mod;

		if (l <= r)
		{
			range.pb({l, 1}); 
			range.pb({r+1, -1});
		}
		else
		{
			range.pb({l, 1});
			range.pb({a*b, -1});
			range.pb({0, 1});
			range.pb({r+1, -1});
		}
	}
	sort(range.begin(), range.end());

	//for (auto x : range)
	//{
	//	cout << "-> " << x.f1 << " " << x.s2 << '\n';
	//}

	ll ctr = 0;
	ll res = 0;
	for (int i = 0; i+1 < range.size(); ++i)
	{
		ctr += range[i].s2;
		if (ctr > 0) res += (range[i+1].f1 - range[i].f1);
	}
	cout << res << '\n';
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:77:22: 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]
   77 |  for (int i = 0; i+1 < range.size(); ++i)
      |                  ~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 1520 KB Output is correct
3 Correct 7 ms 1520 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 396 ms 52676 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 615 ms 54856 KB Output is correct
3 Incorrect 619 ms 54864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 615 ms 54856 KB Output is correct
3 Incorrect 619 ms 54864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 615 ms 54856 KB Output is correct
3 Incorrect 619 ms 54864 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 67 ms 9816 KB Output is correct
3 Correct 66 ms 9872 KB Output is correct
4 Correct 752 ms 54860 KB Output is correct
5 Correct 64 ms 9824 KB Output is correct
6 Correct 65 ms 9820 KB Output is correct
7 Correct 65 ms 9820 KB Output is correct
8 Correct 67 ms 9820 KB Output is correct
9 Correct 65 ms 9820 KB Output is correct
10 Correct 69 ms 9816 KB Output is correct
11 Correct 66 ms 9820 KB Output is correct
12 Correct 58 ms 9820 KB Output is correct
13 Correct 69 ms 9824 KB Output is correct
14 Correct 697 ms 54724 KB Output is correct
15 Correct 69 ms 9820 KB Output is correct
16 Correct 573 ms 86296 KB Output is correct
17 Correct 613 ms 86452 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 1520 KB Output is correct
3 Correct 7 ms 1520 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -