Submission #566832

#	Time	Username	Problem	Language	Result	Execution time	Memory
566832		Aktan	Strange Device (APIO19_strange_device)	C++14	100 / 100	750 ms	100108 KiB

strange_device

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define ft first
#define sc second
const int mod=1e9+7,INF=1e18+10,N=1e5;

main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n,a,b;
	cin >> n >> a >> b;
	int ans=0,tot=a/__gcd(a,b+1);
	if(tot>INF/b){
		tot=INF;
	}
	else{
		tot*=b;
	}
	set<pair<int,int>> s;
	for(int i=0;i<n;i++){
		int l,r;
		cin >> l >> r;
		if(r-l+1>=tot){
			cout << tot ;
			return 0;
		}
		l%=tot;
		r%=tot;
		if(l<=r){
			s.insert({l,r});		
		}
		else{
			s.insert({l,tot-1});
			s.insert({0,r});
		}
	}
	int r=-1;
	for(auto x : s){
		if(r<x.ft){
			ans+=x.sc-x.ft+1;
		}
		else if(r<x.sc){
			ans+=x.sc-r;
		}
		r=max(x.sc,r);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

strange_device.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~

• 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