Submission #252084

#	Time	Username	Problem	Language	Result	Execution time	Memory
252084		jeqcho	Strange Device (APIO19_strange_device)	C++17	35 / 100	616 ms	16120 KiB

strange_device

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
	int n,tot=0;
	LL A,B,len,ans=0;
	struct node{LL l,r;} a[2000010];
LL gcd(LL x,LL y)
{
	return !y?x:gcd(y,x%y);
}
bool cmp(node x,node y)
{
	return x.l==y.l?x.r<y.r:x.l<y.l;
}
int main()
{
	LL l,r;
	scanf("%d %lld %lld",&n,&A,&B);
	len=(A*B/gcd(A,B+1));
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&l,&r);
		if(r-l+1>=len)
		{
			printf("%lld\n",len);
			return 0;
		}
		if(l%len<=r%len) a[++tot]=(node){l%len,r%len}; else a[++tot]=(node){l%len,len-1},a[++tot]=(node){0,r%len};
	}
	sort(a+1,a+tot+1,cmp);
	l=a[1].l,r=a[1].r;
	for(int i=2;i<=tot;i++)
	{
		if(a[i].l>r) {ans+=r-l+1;l=a[i].l,r=a[i].r;continue;}
		r=max(r,a[i].r);
	}
	ans+=r-l+1;
	printf("%lld",ans);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld %lld",&n,&A,&B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30