Submission #972457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
972457	2024-04-30T12:50:24 Z	simona1230	Strange Device (APIO19_strange_device)	C++17	65 / 100	391 ms	17280 KB

strange_device

#include <bits/stdc++.h>

using namespace std;
long long n,a,b;
pair<long long,long long> p[2000001];
void solve()
{
    int cnt=n;
    __int128 h=1e18+1;
    a/=__gcd(a,b+1);
    if(1e18/a>b)h=(__int128)b*(__int128)a;
    //cout<<h<<endl;
    for(long long i=1;i<=n;i++)
    {
        long long l,r;
        cin>>l>>r;
        p[i]={l%(h),r%(h)};
        if(p[i].first>p[i].second)
        {
            cnt++;
            p[cnt].first=0;
            p[cnt].second=p[i].second;

            p[i].second=h-1;
        }
    }
    long long ans=0;
    sort(p+1,p+cnt+1);

    long long r=-1;
    for(long long i=1;i<=cnt;i++)
    {
        if(p[i].second>r)
        {
            if(p[i].first>r)
                ans+=p[i].second-p[i].first+1;
            else ans+=p[i].second-r;
        }

        r=max(r,p[i].second);
    }

    cout<<ans<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>a>>b;
	solve();
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	3 ms	604 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	4 ms	604 KB	Output is correct
17	Correct	32 ms	2656 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	195 ms	17016 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	289 ms	17032 KB	Output is correct
3	Correct	276 ms	16976 KB	Output is correct
4	Correct	317 ms	17276 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	289 ms	17032 KB	Output is correct
3	Correct	276 ms	16976 KB	Output is correct
4	Correct	317 ms	17276 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	283 ms	17032 KB	Output is correct
7	Correct	283 ms	17028 KB	Output is correct
8	Correct	281 ms	17016 KB	Output is correct
9	Correct	315 ms	17232 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	289 ms	17032 KB	Output is correct
3	Correct	276 ms	16976 KB	Output is correct
4	Correct	317 ms	17276 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	30 ms	2648 KB	Output is correct
7	Correct	30 ms	2652 KB	Output is correct
8	Correct	27 ms	2648 KB	Output is correct
9	Correct	31 ms	2688 KB	Output is correct
10	Correct	28 ms	2652 KB	Output is correct
11	Correct	31 ms	2696 KB	Output is correct
12	Correct	28 ms	2652 KB	Output is correct
13	Correct	31 ms	2652 KB	Output is correct
14	Correct	28 ms	2648 KB	Output is correct
15	Correct	31 ms	2652 KB	Output is correct
16	Correct	31 ms	2904 KB	Output is correct
17	Correct	30 ms	2648 KB	Output is correct
18	Correct	291 ms	17280 KB	Output is correct
19	Correct	278 ms	17024 KB	Output is correct
20	Correct	324 ms	17236 KB	Output is correct
21	Correct	31 ms	2652 KB	Output is correct
22	Correct	27 ms	2700 KB	Output is correct
23	Correct	84 ms	6776 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	30 ms	2692 KB	Output is correct
3	Correct	31 ms	2652 KB	Output is correct
4	Correct	391 ms	17040 KB	Output is correct
5	Correct	32 ms	2652 KB	Output is correct
6	Correct	30 ms	2652 KB	Output is correct
7	Correct	30 ms	2648 KB	Output is correct
8	Correct	31 ms	2648 KB	Output is correct
9	Correct	29 ms	2648 KB	Output is correct
10	Correct	32 ms	2900 KB	Output is correct
11	Correct	38 ms	2652 KB	Output is correct
12	Correct	27 ms	2652 KB	Output is correct
13	Correct	32 ms	2648 KB	Output is correct
14	Correct	311 ms	16976 KB	Output is correct
15	Correct	34 ms	2672 KB	Output is correct
16	Correct	270 ms	17032 KB	Output is correct
17	Correct	293 ms	17040 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	3 ms	604 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	4 ms	604 KB	Output is correct
17	Correct	32 ms	2656 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Incorrect	0 ms	348 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #972457

Compilation message