oj.uz

Submission #320939

# Submission time Handle Problem Language Result Execution time Memory
320939 2020-11-10T09:59:27 Z Drew_ Strange Device (APIO19_strange_device) C++14
5 / 100
 746 ms 86340 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;
	}

	vector<pl> range; //first: duration, second: state
	for (pl x : v)
	{
		ll l = x.f1 % (a * b);
		ll r = x.s2 % (a * b);

		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:67: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]
   67 |  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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 420 ms 74180 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 597 ms 86340 KB Output is correct
3 Incorrect 554 ms 86220 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 597 ms 86340 KB Output is correct
3 Incorrect 554 ms 86220 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 597 ms 86340 KB Output is correct
3 Incorrect 554 ms 86220 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 63 ms 9948 KB Output is correct
3 Correct 63 ms 9820 KB Output is correct
4 Correct 746 ms 86200 KB Output is correct
5 Correct 65 ms 9820 KB Output is correct
6 Correct 63 ms 9948 KB Output is correct
7 Correct 62 ms 9820 KB Output is correct
8 Correct 64 ms 9948 KB Output is correct
9 Correct 61 ms 9896 KB Output is correct
10 Correct 65 ms 9820 KB Output is correct
11 Correct 65 ms 9824 KB Output is correct
12 Correct 56 ms 9820 KB Output is correct
13 Correct 65 ms 9820 KB Output is correct
14 Correct 690 ms 86196 KB Output is correct
15 Incorrect 65 ms 9820 KB Output isn't correct
16 Halted 0 ms 0 KB -

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 -