oj.uz

Submission #255064

# Submission time Handle Problem Language Result Execution time Memory
255064 2020-07-31T07:36:46 Z BamiTorabi Strange Device (APIO19_strange_device) C++14
15 / 100
 586 ms 38904 KB 
//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 2e6 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int cnt = 0, len = 0;
pll P[maxN], Q[maxN];

ll gcd(ll a, ll b){
	return (b == 0 ? a : gcd(b, a % b));
}

pll I(pll X, pll Y){
	if (X > Y)
		swap(X, Y);
	pll Z;
	Z.first = Y.first;
	Z.second = X.second;
	if (Z.first > Z.second)
		Z = {-1, -1};
	return Z;
}

pll U(pll X, pll Y){
	if (X > Y)
		swap(X, Y);
	pll Z;
	Z.first = X.first;
	Z.second = Y.second;
	return Z;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; ll A, B; scanf("%d%lld%lld", &n, &A, &B);
	ll g = gcd(A, B + 1);
	ll L = (B / g <= INF / A ? A * B / g : INF);
	while (n--){
		ll l, r; scanf("%lld%lld", &l, &r);
		if (L <= (r - l + 1))
			return printf("%lld\n", L), 0;
		if (A <= l / B)
			l %= L;
		if (A <= r / B)
			r %= L;
		if (r >= l)
			P[cnt++] = {l, r};
		else{
			P[cnt++] = {l, L - 1};
			P[cnt++] = {0, r};
		}
	}
	sort(P, P + cnt);
	Q[0] = P[0];
	for (int i = 1; i < cnt; i++){
		if (I(Q[len], P[i]).first == -1)
			Q[++len] = P[i];
		else
			Q[len] = U(Q[len], P[i]);
	}
	ll ans = len + 1;
	for (int i = 0; i <= len; i++)
		ans += Q[i].second - Q[i].first;
	printf("%lld\n", ans);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:61:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; ll A, B; scanf("%d%lld%lld", &n, &A, &B);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll l, r; scanf("%lld%lld", &l, &r);
            ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 532 ms 33144 KB Output is correct
3 Correct 518 ms 33128 KB Output is correct
4 Correct 533 ms 38692 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 532 ms 33144 KB Output is correct
3 Correct 518 ms 33128 KB Output is correct
4 Correct 533 ms 38692 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 521 ms 38776 KB Output is correct
7 Correct 540 ms 38904 KB Output is correct
8 Correct 557 ms 38740 KB Output is correct
9 Correct 585 ms 38580 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 532 ms 33144 KB Output is correct
3 Correct 518 ms 33128 KB Output is correct
4 Correct 533 ms 38692 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 56 ms 7160 KB Output is correct
7 Correct 58 ms 7160 KB Output is correct
8 Correct 51 ms 7160 KB Output is correct
9 Correct 53 ms 7160 KB Output is correct
10 Correct 55 ms 7160 KB Output is correct
11 Correct 61 ms 7160 KB Output is correct
12 Correct 52 ms 7160 KB Output is correct
13 Correct 54 ms 7160 KB Output is correct
14 Correct 54 ms 7160 KB Output is correct
15 Incorrect 59 ms 7160 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 57 ms 4216 KB Output is correct
3 Correct 54 ms 4216 KB Output is correct
4 Correct 586 ms 33144 KB Output is correct
5 Correct 52 ms 4216 KB Output is correct
6 Correct 53 ms 4248 KB Output is correct
7 Correct 51 ms 4228 KB Output is correct
8 Correct 55 ms 4216 KB Output is correct
9 Correct 53 ms 4216 KB Output is correct
10 Correct 54 ms 4216 KB Output is correct
11 Correct 54 ms 4216 KB Output is correct
12 Correct 48 ms 4216 KB Output is correct
13 Correct 56 ms 4216 KB Output is correct
14 Incorrect 567 ms 33144 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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