Submission #764729

#	Time	Username	Problem	Language	Result	Execution time	Memory
764729		KN200711	Strange Device (APIO19_strange_device)	C++14	100 / 100	392 ms	53348 KiB

strange_device

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

int main() {
	int N;
	ll A, B;
	scanf("%d %lld %lld", &N, &A, &B);
	
	ll P = A / __gcd(A, B + 1ll);
	vector< pair<ll, ll> > ln;
	ln.clear();
	
	ll BC = 0ll;
	
	bool cek = 1;
	if(1e18 / B >= P) BC = B * P;
	else cek = 0;
	
//	cout<<cek<<" "<<BC<<endl;
	
	ll ans = 0ll;
	for(int i=0;i<N;i++) {
		ll L, R;
		scanf("%lld %lld", &L, &R);
		if(cek && (R - L + 1) >= BC) {
			printf("%lld\n", BC);
			return 0;
		}
		if(!cek) ans += R - L + 1ll;
		else {
			if(L%BC <= R%BC) {
				ln.push_back(make_pair(L%BC, R%BC));
			} else {
				ln.push_back(make_pair(L%BC, BC - 1));
				ln.push_back(make_pair(0, R%BC));
			}
		}
	}
	
	if(!cek) printf("%lld\n", ans);
	else {
		sort(ln.begin(), ln.end());
		ll nw = -1ll, as = 0ll;
		for(auto p : ln) {
		//	cout<<p.fi<<" "<<p.se<<endl;
			if(nw < p.fi) {
				as += p.se - p.fi + 1ll; 
			} else if(nw < p.se) {
				as += p.se - nw;
			}
			nw = max(nw, p.se);
		}
		printf("%lld\n", as);
		return 0;
	}
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%d %lld %lld", &N, &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%lld %lld", &L, &R);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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