oj.uz

Submission #252084

# Submission time Handle Problem Language Result Execution time Memory
252084 2020-07-24T06:09:39 Z jeqcho Strange Device (APIO19_strange_device) C++17
35 / 100
 616 ms 16120 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 63 ms 1912 KB Output is correct
18 Incorrect 0 ms 256 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Incorrect 0 ms 256 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 430 ms 15992 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 542 ms 16120 KB Output is correct
3 Correct 546 ms 16120 KB Output is correct
4 Correct 540 ms 16120 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 542 ms 16120 KB Output is correct
3 Correct 546 ms 16120 KB Output is correct
4 Correct 540 ms 16120 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 536 ms 15992 KB Output is correct
7 Correct 550 ms 15992 KB Output is correct
8 Correct 537 ms 16120 KB Output is correct
9 Correct 596 ms 15992 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 542 ms 16120 KB Output is correct
3 Correct 546 ms 16120 KB Output is correct
4 Correct 540 ms 16120 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 55 ms 1912 KB Output is correct
7 Correct 60 ms 1860 KB Output is correct
8 Correct 50 ms 1912 KB Output is correct
9 Correct 54 ms 1912 KB Output is correct
10 Correct 53 ms 1912 KB Output is correct
11 Correct 54 ms 1912 KB Output is correct
12 Correct 50 ms 1912 KB Output is correct
13 Correct 57 ms 1912 KB Output is correct
14 Correct 51 ms 1912 KB Output is correct
15 Correct 78 ms 1912 KB Output is correct
16 Correct 69 ms 1912 KB Output is correct
17 Correct 55 ms 1912 KB Output is correct
18 Correct 566 ms 15992 KB Output is correct
19 Correct 514 ms 16120 KB Output is correct
20 Correct 616 ms 16084 KB Output is correct
21 Correct 56 ms 1912 KB Output is correct
22 Correct 49 ms 1912 KB Output is correct
23 Correct 186 ms 5624 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 59 ms 1912 KB Output is correct
3 Correct 58 ms 1916 KB Output is correct
4 Correct 615 ms 15992 KB Output is correct
5 Correct 56 ms 1912 KB Output is correct
6 Correct 56 ms 1912 KB Output is correct
7 Correct 56 ms 1912 KB Output is correct
8 Correct 61 ms 1912 KB Output is correct
9 Correct 55 ms 1912 KB Output is correct
10 Correct 56 ms 1912 KB Output is correct
11 Correct 59 ms 1912 KB Output is correct
12 Correct 48 ms 1912 KB Output is correct
13 Correct 57 ms 1920 KB Output is correct
14 Correct 604 ms 15992 KB Output is correct
15 Correct 57 ms 1912 KB Output is correct
16 Correct 551 ms 15908 KB Output is correct
17 Correct 544 ms 15992 KB Output is correct
18 Incorrect 0 ms 256 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 63 ms 1912 KB Output is correct
18 Incorrect 0 ms 256 KB Output isn't correct