oj.uz

Submission #255065

# Submission time Handle Problem Language Result Execution time Memory
255065 2020-07-31T07:38:30 Z BamiTorabi Strange Device (APIO19_strange_device) C++14
15 / 100
 615 ms 31868 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 (l >= L)
			l %= L;
		if (r >= L)
			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 5 ms 640 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 1 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 1 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 1 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 509 ms 31736 KB Output is correct
3 Correct 509 ms 31600 KB Output is correct
4 Correct 500 ms 31668 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 509 ms 31736 KB Output is correct
3 Correct 509 ms 31600 KB Output is correct
4 Correct 500 ms 31668 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 493 ms 31864 KB Output is correct
7 Correct 508 ms 31864 KB Output is correct
8 Correct 495 ms 31736 KB Output is correct
9 Correct 545 ms 31868 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 509 ms 31736 KB Output is correct
3 Correct 509 ms 31600 KB Output is correct
4 Correct 500 ms 31668 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 49 ms 3448 KB Output is correct
7 Correct 55 ms 3576 KB Output is correct
8 Correct 48 ms 3448 KB Output is correct
9 Correct 50 ms 3448 KB Output is correct
10 Correct 53 ms 3448 KB Output is correct
11 Correct 53 ms 3448 KB Output is correct
12 Correct 50 ms 3468 KB Output is correct
13 Correct 52 ms 3448 KB Output is correct
14 Correct 51 ms 3448 KB Output is correct
15 Incorrect 54 ms 3448 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 62 ms 3532 KB Output is correct
3 Correct 56 ms 3448 KB Output is correct
4 Correct 615 ms 31776 KB Output is correct
5 Correct 75 ms 3448 KB Output is correct
6 Correct 52 ms 3448 KB Output is correct
7 Correct 54 ms 3448 KB Output is correct
8 Correct 54 ms 3448 KB Output is correct
9 Correct 50 ms 3448 KB Output is correct
10 Correct 63 ms 3576 KB Output is correct
11 Correct 55 ms 3448 KB Output is correct
12 Correct 47 ms 3448 KB Output is correct
13 Correct 54 ms 3448 KB Output is correct
14 Incorrect 551 ms 31636 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 5 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -