Submission #767214

#	Time	Username	Problem	Language	Result	Execution time	Memory
767214		Trisanu_Das	Strange Device (APIO19_strange_device)	C++17	100 / 100	1391 ms	100212 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

int n,curr;
ll a,b,ans,l,r,cc,pre=-1;
lll cyc;
map<ll,int> todo;

int main(){
	cin>>n>>a>>b;
	cyc=a/__gcd(a,b+1);
	cyc*=b;
	if (cyc>=LLONG_MAX) cc=LLONG_MAX;
	else cc=cyc;
	for (int i=1;i<=n;i++){
		cin>>l>>r;
		if (r-l>=cc){
			cout<<cc<<"\n";
			return 0;
		}
		if (l/cc!=r/cc){
			todo[l%cc]++;
			todo[cc]--;
			todo[0]++;
			todo[r%cc+1]--;
		}else{
			todo[l%cc]++;
			todo[r%cc+1]--;
		}
	}
	for (auto i:todo){
		if (curr) ans+=i.first-pre;
		curr+=i.second;
		pre=i.first;
	}
	cout<<ans<<"\n";
}

• 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