Submission #167998

#	Time	Username	Problem	Language	Result	Execution time	Memory
167998		kostia244	Strange Device (APIO19_strange_device)	C++17	100 / 100	1266 ms	86316 KiB

strange_device

#pragma GCC optimize("trapv")
#include<bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll n, a, b, s = 0, c;
vector<pi> seg;
ll solve1() {
	set<pair<int, int>> have;
	for(auto &i : seg) {
		for(int j = i.first; j <= i.second; j++) {
			have.insert({j%b, (j + j/b)%a});
		}
	}
	int ans = 0;
	for(auto &i : have)
		ans++;
	return ans;
}
ll solve2() {
	return min(s, c);
}
ll solve() {
	vector<pair<ll, ll>> a;
	for(auto i : seg) {
		if(i.second-i.first+1>=c) return c;
		ll x = i.first%c, y = i.second%c;
//		cout << x << " " << y << "\n";
		if(x<=y) {
			a.pb({x, 1});
			a.pb({y+1, 0});
//			cout << x << " " << y+1 << ")\n";
		} else {
			a.pb({0, 1});
			a.pb({y+1, 0});
			a.pb({x, 1});
			a.pb({c, 0});
		}
	}
	sort(all(a));
	ll ans = 0, op = 0;
	for(int i = 0; i +1 < a.size(); i++) {
		op += (a[i].second?1:-1);
		if(op) ans += a[i+1].first-a[i].first;
//		cout << a[i].first << " " << a[i].second << "\n";// << op << " " << ans << "\n";
	}
	return ans;
}
void tst() {
	for(int i = 0; i < 100; i++) {
		int l = rng()%100000, r = l + (rng()%100000);
		n = 1, a = rng()%100000, b = rng()%100000;
		seg = {{l, r}};
		s = r-l+1;
		assert(solve1()==solve());
//		cout << solve1() << " " << solve2() << "\n";
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> a >> b;
	seg.resize(n);
	for(auto &i : seg) {
		cin >> i.first >> i.second;
		s += i.second-i.first+1;
	}
	if((a/__gcd(a, b)) > 2000000000000000000/b) return cout << s, 0;
	c = b*(a/__gcd(a, b+1));
	return cout << solve(), 0;
	if(s<=1000000) return cout << solve1(), 0;
	if(n==1) return cout << solve2(), 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'll solve1()':
strange_device.cpp:20:12: warning: unused variable 'i' [-Wunused-variable]
  for(auto &i : have)
            ^
strange_device.cpp: In function 'll solve()':
strange_device.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i +1 < a.size(); i++) {
                 ~~~~~^~~~~~~~~~

• 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