Submission #1174525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174525		tkm_algorithms	Strange Device (APIO19_strange_device)	C++20	0 / 100	5092 ms	589824 KiB

strange_device

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
//const char nl = '\n';
const int N = 1e7;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, a, b;
	cin >> n >> a >> b;
	
	if (b == 1) {
		set<pair<int, int>> st, st2;
		for (int i = 0; i < n; ++i) {
			int l, r; cin >> l >> r;
			if (sz(st) == 0)st.insert({l, r}), st2.insert({r, l});
			else {
				auto it = st.lower_bound({l, 0});
				int nl = l, nr = r;
				while (it != st.end() && it->first <= r) {
					nl = min(l, it->first);
					nr = max(r, it->second);
					st2.erase({it->second, it->first});
					st.erase(it);
					it = st.lower_bound({l, 0});
				}
				
				st.insert({nl, nr});
				st2.insert({nr, nl});
				
				nl = l, nr = r;
				it = st2.lower_bound({l, 0});
				while (it != st2.end() && it->first >= l && it->first <= r) {
					nl = min(l, it->second);
					nr = max(r, it->first);
					st.erase({nl, nr});
					st2.erase(it);
					it = st2.lower_bound({l, 0});
				}
				st2.insert({nr, nl});
				st.insert({nl, nr});
			}
		}
		int ans = 0;
		
		for (auto i: st) {
			//cout << i.first << " " << i.second << endl;
			ans += i.second-i.first+1;
		}	
		cout << ans;
		return 0;
	}
	
	set<pair<int, int>> st;
	for (int i = 0; i < n; ++i) {
		int l, r; cin >> l >> r;
		
		for (int j = l; j <= r; ++j)st.insert({(j+j/b)%a, j%b});
	}
	cout << sz(st);
	return 0;
}

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