Submission #187027

#	Time	Username	Problem	Language	Result	Execution time	Memory
187027		KCSC	Strange Device (APIO19_strange_device)	C++14	100 / 100	3228 ms	48512 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

const int DIM = 2e6 + 5;

int psm[DIM];

vector<pair<long long, long long>> seg;
vector<long long> crd;

long long gcd(long long a, long long b) {
	return !b ? a : gcd(b, a % b);
}

int main(void) {
#ifdef HOME
	freopen("device.in", "r", stdin);
	freopen("device.out", "w", stdout);
#endif
	int n; long long A, B;
	cin >> n >> A >> B;
	long long _A = A, _B = B;
	long long g = gcd(A, B + 1); A /= g;
	long long p;
	if ((1LL << 61) / A >= B)
		p = A * B;
	else
		p = 1LL << 61;
	#ifdef HOME
	for (int i = 0; i <= p * 10; ++i) {
		if (i % p == 0)
			cout << endl;
		cout << (i + i / _B) % _A << " " << i % B << " ";
	}
	#endif
	for (int i = 1; i <= n; ++i) {
		long long le, ri;
		cin >> le >> ri;
		if (ri - le + 1 >= p) {
			cout << p << endl;
			return 0; 
		} else 
		if (ri / p * p == le / p * p) 
			seg.push_back(make_pair(le % p, ri % p));
		else {
			seg.push_back(make_pair(le % p, p - 1));
			seg.push_back(make_pair(0, ri % p));
		}
	}
	for (pair<long long, long long> sg : seg) {
		crd.push_back(sg.first);
		crd.push_back(sg.second + 1);
	}
	sort(crd.begin(), crd.end());
	crd.resize(unique(crd.begin(), crd.end()) - crd.begin());
	for (pair<long long, long long> sg : seg) {
		int p1 = lower_bound(crd.begin(), crd.end(), sg.first) - crd.begin() + 1,
				p2 = lower_bound(crd.begin(), crd.end(), sg.second + 1) - crd.begin() + 1;
		++psm[p1]; --psm[p2];
	}
	long long ans = 0;
	for (int i = 1; i < crd.size(); ++i) {
		psm[i] += psm[i - 1];
		if (psm[i] > 0) 
			ans += crd[i] - crd[i - 1];
	}
	cout << ans << endl;	
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < crd.size(); ++i) {
                  ~~^~~~~~~~~~~~
strange_device.cpp:22:12: warning: unused variable '_A' [-Wunused-variable]
  long long _A = A, _B = B;
            ^~
strange_device.cpp:22:20: warning: unused variable '_B' [-Wunused-variable]
  long long _A = A, _B = B;
                    ^~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30