Submission #166416

#	Time	Username	Problem	Language	Result	Execution time	Memory
166416		Feeder	Strange Device (APIO19_strange_device)	C++11	100 / 100	817 ms	53628 KiB

strange_device

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	vector<pair<ll, ll> > vec;
	ll l, r, a, b, d, m, l2, r2, out = 0;
	cin >> n >> a >> b;
	d = a / __gcd(a, b+ 1);
	if(1e18 / b <= d) m = 1e18;
	else m = b * d;
	for(int i=0; i<n; i++){
		cin >> l >> r;
		l2 = r2 = -1;
		if(r / m == l / m) r %= m, l %= m;
		else if(r / m == l / m + 1){
			if(r % m + 1 >= l % m) l = 0, r = m - 1;
			else{
				l %= m, r %= m;
				l2 = 0, r2 = r;
				r = m - 1;
			}
		}
		else l = 0, r = m - 1;
		vec.emplace_back(l, r);
		if(l2 != -1) vec.emplace_back(l2, r2);
	}
	sort(vec.begin(), vec.end());
	l = r = -1;
	for(int i=0; i<vec.size(); i++){
		tie(a, b) = vec[i];
		if(a > r){
			l = a, r = b;
			out += (b - a + 1);
		}
		else if(b > r){
			out += (b - r);
			r = b;
		}			
	}
	cout << out;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vec.size(); 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