Submission #367993

#	Time	Username	Problem	Language	Result	Execution time	Memory
367993		grt	Strange Device (APIO19_strange_device)	C++17	100 / 100	776 ms	42688 KiB

strange_device

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const ll INF = 1e18 + 10;
int n;
ll a, b;
vector<pair<ll,int>>p;

ll mul(ll aa, ll ba) {
	if(ba == 0) return 0LL;
	if(ba & 1) {
		return min(INF, 2 * mul(aa, ba/2) + aa);
	} else {
		return min(INF, 2 * mul(aa, ba/2));
	}
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> a >> b;
	ll g = __gcd(a, b + 1);
	a /= g;
	ll mod = mul(a, b);
	
	for(int i = 1; i <= n; ++i) {
		ll l, r;
		cin >> l >> r;
		if(r - l + 1 >= mod) {
			p.PB({0,1});
			p.PB({mod,-1});
		} else {
			if(l % (mod) <= r % (mod)) {
				p.PB({l % (mod), 1});
				p.PB({(r % (mod)) + 1, -1});
			} else {
				p.PB({(l % (mod)), 1});
				p.PB({mod, -1});
				p.PB({0, 1});
				p.PB({r % (mod) + 1, -1});
			}
		}
	}
	sort(p.begin(), p.end());
	ll ans = 0;
	int cnt = 0;
	ll pr = 0;
	for(auto it : p) {
		if(cnt > 0) ans += it.ST - pr;
		cnt += it.ND;
		pr = it.ST;
	}
	cout << ans;
}

• 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