Submission #172126

#	Time	Username	Problem	Language	Result	Execution time	Memory
172126		dennisstar	Strange Device (APIO19_strange_device)	C++11	100 / 100	596 ms	17040 KiB

strange_device

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

vector<pll> V;
const ll INF=(1e18)+10;
int n; ll A, B;
ll l, r;

int main() {
	scanf("%d %lld %lld", &n, &A, &B);
	A/=__gcd(A, B+1);
	if ((ll)(1e18)/B<A) A=INF;
	else A*=B;
	for (int i=0; i<n; i++) {
		scanf("%lld %lld", &l, &r);
		if (r-l+1>=A) V.push_back({0, A-1});
		else {
			r=(r-l)+l%A;
			l%=A;
			if (r>=A) {
				V.push_back({l, A-1});
				V.push_back({0, r-A});
			}
			else V.push_back({l, r});
		}
	}
	ll mx=0, ans=0; sort(all(V));
	for (pll pl:V) {
		ans+=max(0ll, pl.se-max(pl.fi, mx)+1);
		mx=max(pl.se+1, mx);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld %lld", &n, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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