Submission #1035275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035275		KasymK	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	334 ms	69820 KiB

strange_device

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int MOD = 1e9+7;
const int N = 1e6+5;
ll l[N], r[N];

int main(){
	int n;
	ll a, b;
	scanf("%d %lld %lld", &n, &a, &b);
	__int128 m = (__int128)a/__gcd(a, b+1)*b;
	for(int i = 1 ; i <= n; ++i)
		scanf("%lld %lld", &l[i], &r[i]);
	vector<pll> v;
	for(int i = 1; i <= n; ++i){
		if(r[i]-l[i]+1 >= m)
			v.pb({0, m-1});
		else if(l[i]%m > r[i]%m)
			v.pb({l[i]%m, m-1}), v.pb({0, r[i]%m});
		else
			v.pb({l[i]%m, r[i]%m});
	}
	sort(all(v));
	ll l_ = v[0].ff, r_ = v[0].ss;
	ll answer = 0;
	int n_ = (int)v.size();
	for(int i = 0; i < n_; ++i){
		// I am doing kerim's technique instead of sweep line
		// because Kerim's technique is O(n), but sweep line is O(nlog(n)) in worst case
		// because in sweep line we use like set data structure's
		if(v[i].ff <= r_)
			umax(r_, v[i].ss);
		else
			answer += (r_-l_+1), l_ = v[i].ff, r_ = v[i].ss;
	}
	answer += (r_-l_+1);
	printf("%lld\n", answer);
	return 0;
}

Compilation message (stderr)

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