Submission #206799

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
206799	2020-03-05T12:05:27 Z	rkm0959	Strange Device (APIO19_strange_device)	C++14	65 / 100	609 ms	33920 KB

strange_device

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef long double ldb;
ll gcd(ll x,ll y){if(!x||!y) return x+y; return x%y==0?y:gcd(y,x%y);}

ll n, A, B, inf=2e18, ans;
pair<ll, ll> wow[2111111];

int main(void)
{
	fio; ll i, j, u, v, cnt=0;
	cin>>n>>A>>B; ll g=gcd(A, B+1);
	__int128 cc=(A/g); cc=cc*B;
	for(i=1 ; i<=n ; i++)
	{
		cin>>u>>v;
		if(cc>=inf) { wow[++cnt]=make_pair(u, v); continue; }
		u=(ll)(u%cc); v=(ll)(v%cc);
		if(u<=v) wow[++cnt]=make_pair(u, v);
		if(u>v)
		{
			wow[++cnt]=make_pair(u, (ll)cc-1LL);
			wow[++cnt]=make_pair(0LL, v);
		}
	}
	sort(wow+1, wow+cnt+1);
	for(i=1 ; i<=cnt ; i++)
	{
		j=i; ll rng=wow[i].second;
		while(j<=cnt && wow[j].first<=rng)
			{ rng=max(rng, wow[j].second); j++; }
		j--; ans+=(rng-wow[i].first+1); i=j;
	}
	cout<<ans; return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	10 ms	884 KB	Output is correct
3	Correct	10 ms	888 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	6 ms	376 KB	Output is correct
7	Correct	5 ms	380 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	10 ms	888 KB	Output is correct
17	Correct	61 ms	5624 KB	Output is correct
18	Correct	5 ms	248 KB	Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	508 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	372 ms	21496 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	536 ms	33912 KB	Output is correct
3	Correct	513 ms	33920 KB	Output is correct
4	Correct	517 ms	23372 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	536 ms	33912 KB	Output is correct
3	Correct	513 ms	33920 KB	Output is correct
4	Correct	517 ms	23372 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	555 ms	23160 KB	Output is correct
7	Correct	571 ms	23928 KB	Output is correct
8	Correct	560 ms	23416 KB	Output is correct
9	Correct	609 ms	23960 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	536 ms	33912 KB	Output is correct
3	Correct	513 ms	33920 KB	Output is correct
4	Correct	517 ms	23372 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	57 ms	5604 KB	Output is correct
7	Correct	60 ms	5624 KB	Output is correct
8	Correct	57 ms	5624 KB	Output is correct
9	Correct	60 ms	5624 KB	Output is correct
10	Correct	55 ms	5624 KB	Output is correct
11	Correct	61 ms	5624 KB	Output is correct
12	Correct	57 ms	5624 KB	Output is correct
13	Correct	61 ms	5624 KB	Output is correct
14	Correct	57 ms	5624 KB	Output is correct
15	Correct	60 ms	5596 KB	Output is correct
16	Correct	61 ms	5624 KB	Output is correct
17	Correct	61 ms	5624 KB	Output is correct
18	Correct	528 ms	23452 KB	Output is correct
19	Correct	527 ms	23788 KB	Output is correct
20	Correct	597 ms	23548 KB	Output is correct
21	Correct	64 ms	5624 KB	Output is correct
22	Correct	56 ms	5624 KB	Output is correct
23	Correct	191 ms	18304 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	65 ms	5644 KB	Output is correct
3	Correct	69 ms	5624 KB	Output is correct
4	Correct	602 ms	23600 KB	Output is correct
5	Correct	66 ms	5624 KB	Output is correct
6	Correct	60 ms	5624 KB	Output is correct
7	Correct	62 ms	5876 KB	Output is correct
8	Correct	63 ms	5624 KB	Output is correct
9	Correct	61 ms	5624 KB	Output is correct
10	Correct	62 ms	5584 KB	Output is correct
11	Correct	63 ms	5624 KB	Output is correct
12	Correct	54 ms	5624 KB	Output is correct
13	Correct	62 ms	5664 KB	Output is correct
14	Correct	587 ms	23380 KB	Output is correct
15	Correct	61 ms	5624 KB	Output is correct
16	Correct	516 ms	23268 KB	Output is correct
17	Correct	517 ms	23304 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	10 ms	884 KB	Output is correct
3	Correct	10 ms	888 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	6 ms	376 KB	Output is correct
7	Correct	5 ms	380 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	10 ms	888 KB	Output is correct
17	Correct	61 ms	5624 KB	Output is correct
18	Correct	5 ms	248 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Incorrect	5 ms	376 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #206799

Compilation message