Submission #120565

#	Time	Username	Problem	Language	Result	Execution time	Memory
120565		nandonathaniel	Strange Device (APIO19_strange_device)	C++14	100 / 100	687 ms	68936 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=2e18;
const LL MAXN=2e6+5;

LL kali(LL a,LL b){
	if(b==1)return a;
	LL ret=kali(a,b/2);
	ret=min(INF,2LL*ret);
	if(b&1)ret=min(INF,ret+a);
	return ret;
}

LL L[MAXN],R[MAXN];
pair<LL,LL> isi[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	LL n,A,B;
	cin >> n >> A >> B;
	for(LL i=1;i<=n;i++){
		cin >> L[i] >> R[i];
	}
	LL p=kali(A/__gcd(A,B+1),B);
	LL baru=n+1;
	for(LL i=1;i<=n;i++){
		if(R[i]-L[i]+1>=p){
			cout << p << endl;
			return 0;
		}
		L[i]%=p;
		R[i]%=p;
		if(R[i]<L[i]){
			L[baru]=0;
			R[baru]=R[i];
			R[i]=p-1;
			baru++;
		}
	}
	baru--;
	for(LL i=1;i<=baru;i++)isi[i]={L[i],R[i]};
	sort(isi+1,isi+baru+1);
	LL ans=isi[1].second-isi[1].first+1,last=isi[1].second;
	for(LL i=2;i<=baru;i++){
		ans+=(max(last,isi[i].second)-max(last,isi[i].first-1));
		last=max(last,isi[i].second);
	}
	cout << ans << endl;
	return 0;
}

• 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