Submission #972437

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
972437	2024-04-30T12:24:16 Z	simona1230	Strange Device (APIO19_strange_device)	C++17	65 / 100	357 ms	36176 KB

strange_device

#include <bits/stdc++.h>

using namespace std;
long long n,a,b;
map<pair<long long,long long>,long long> mp;
void help()
{

    for(long long t=0;t<=110;t++)
    {
        long long x=(t+t/b)%a,y=t%b;
        if(mp[{x,y}])
            {
                cout<<t<<" "<<x<<" "<<y<<" "<<mp[{x,y}]<<endl;
            }
        mp[{x,y}]=t+1;
    }
}

pair<long long,long long> p[2000001];
void solve()
{
    int cnt=n;
    long long h=1e18+1;
    if(1e18/a>=b)h=b*a/__gcd(a,b+1);
    if(h<0)h=1e18+1;
    //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;

	//help();
	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	860 KB	Output is correct
3	Correct	3 ms	840 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	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 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	468 KB	Output is correct
16	Correct	4 ms	992 KB	Output is correct
17	Correct	33 ms	4712 KB	Output is correct
18	Correct	0 ms	356 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	356 KB	Output is correct
2	Incorrect	356 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	356 KB	Output is correct
2	Correct	1 ms	356 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	356 KB	Output is correct
5	Correct	201 ms	29588 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	298 ms	35724 KB	Output is correct
3	Correct	292 ms	35716 KB	Output is correct
4	Correct	294 ms	35728 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	298 ms	35724 KB	Output is correct
3	Correct	292 ms	35716 KB	Output is correct
4	Correct	294 ms	35728 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	287 ms	35712 KB	Output is correct
7	Correct	318 ms	35636 KB	Output is correct
8	Correct	278 ms	35688 KB	Output is correct
9	Correct	357 ms	36176 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	298 ms	35724 KB	Output is correct
3	Correct	292 ms	35716 KB	Output is correct
4	Correct	294 ms	35728 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	37 ms	4700 KB	Output is correct
7	Correct	30 ms	4700 KB	Output is correct
8	Correct	28 ms	4556 KB	Output is correct
9	Correct	28 ms	4672 KB	Output is correct
10	Correct	29 ms	4692 KB	Output is correct
11	Correct	31 ms	4700 KB	Output is correct
12	Correct	32 ms	4788 KB	Output is correct
13	Correct	31 ms	4696 KB	Output is correct
14	Correct	35 ms	4696 KB	Output is correct
15	Correct	34 ms	4684 KB	Output is correct
16	Correct	32 ms	4696 KB	Output is correct
17	Correct	29 ms	4700 KB	Output is correct
18	Correct	298 ms	35820 KB	Output is correct
19	Correct	280 ms	35668 KB	Output is correct
20	Correct	323 ms	35520 KB	Output is correct
21	Correct	31 ms	4720 KB	Output is correct
22	Correct	26 ms	4672 KB	Output is correct
23	Correct	87 ms	13376 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	532 KB	Output is correct
2	Correct	32 ms	4572 KB	Output is correct
3	Correct	31 ms	4584 KB	Output is correct
4	Correct	345 ms	35716 KB	Output is correct
5	Correct	30 ms	4696 KB	Output is correct
6	Correct	31 ms	4688 KB	Output is correct
7	Correct	30 ms	4708 KB	Output is correct
8	Correct	40 ms	4696 KB	Output is correct
9	Correct	30 ms	4720 KB	Output is correct
10	Correct	30 ms	4700 KB	Output is correct
11	Correct	31 ms	4700 KB	Output is correct
12	Correct	31 ms	4716 KB	Output is correct
13	Correct	31 ms	4700 KB	Output is correct
14	Correct	314 ms	35936 KB	Output is correct
15	Correct	32 ms	4700 KB	Output is correct
16	Correct	284 ms	35688 KB	Output is correct
17	Correct	280 ms	35820 KB	Output is correct
18	Correct	0 ms	460 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	860 KB	Output is correct
3	Correct	3 ms	840 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	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 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	468 KB	Output is correct
16	Correct	4 ms	992 KB	Output is correct
17	Correct	33 ms	4712 KB	Output is correct
18	Correct	0 ms	356 KB	Output is correct
19	Correct	0 ms	356 KB	Output is correct
20	Incorrect	0 ms	356 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #972437

Compilation message