Submission #972430

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
972430	2024-04-30T12:04:19 Z	simona1230	Strange Device (APIO19_strange_device)	C++17	65 / 100	356 ms	54620 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*(b+1)/__gcd(a,b+1)/(b+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	1 ms	344 KB	Output is correct
2	Correct	5 ms	860 KB	Output is correct
3	Correct	4 ms	856 KB	Output is correct
4	Correct	0 ms	468 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	376 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 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	3 ms	860 KB	Output is correct
17	Correct	32 ms	6236 KB	Output is correct
18	Correct	0 ms	344 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	348 KB	Output is correct
2	Correct	1 ms	432 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	516 KB	Output is correct
5	Correct	199 ms	41972 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	54128 KB	Output is correct
3	Correct	285 ms	54352 KB	Output is correct
4	Correct	298 ms	54360 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	54128 KB	Output is correct
3	Correct	285 ms	54352 KB	Output is correct
4	Correct	298 ms	54360 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	286 ms	54036 KB	Output is correct
7	Correct	340 ms	53992 KB	Output is correct
8	Correct	286 ms	54404 KB	Output is correct
9	Correct	315 ms	53996 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	54128 KB	Output is correct
3	Correct	285 ms	54352 KB	Output is correct
4	Correct	298 ms	54360 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	30 ms	6228 KB	Output is correct
7	Correct	31 ms	6228 KB	Output is correct
8	Correct	28 ms	6224 KB	Output is correct
9	Correct	29 ms	6228 KB	Output is correct
10	Correct	29 ms	6228 KB	Output is correct
11	Correct	31 ms	6384 KB	Output is correct
12	Correct	28 ms	6372 KB	Output is correct
13	Correct	31 ms	6228 KB	Output is correct
14	Correct	29 ms	6228 KB	Output is correct
15	Correct	32 ms	6392 KB	Output is correct
16	Correct	33 ms	6236 KB	Output is correct
17	Correct	30 ms	6356 KB	Output is correct
18	Correct	294 ms	54180 KB	Output is correct
19	Correct	280 ms	53988 KB	Output is correct
20	Correct	325 ms	54456 KB	Output is correct
21	Correct	31 ms	6232 KB	Output is correct
22	Correct	27 ms	6228 KB	Output is correct
23	Correct	82 ms	19284 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	32 ms	6224 KB	Output is correct
3	Correct	31 ms	6228 KB	Output is correct
4	Correct	356 ms	54096 KB	Output is correct
5	Correct	30 ms	6236 KB	Output is correct
6	Correct	31 ms	6492 KB	Output is correct
7	Correct	30 ms	6228 KB	Output is correct
8	Correct	33 ms	6228 KB	Output is correct
9	Correct	30 ms	6236 KB	Output is correct
10	Correct	38 ms	6236 KB	Output is correct
11	Correct	30 ms	6224 KB	Output is correct
12	Correct	26 ms	6224 KB	Output is correct
13	Correct	30 ms	6380 KB	Output is correct
14	Correct	330 ms	54232 KB	Output is correct
15	Correct	34 ms	6236 KB	Output is correct
16	Correct	280 ms	53984 KB	Output is correct
17	Correct	288 ms	54620 KB	Output is correct
18	Correct	1 ms	344 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	5 ms	860 KB	Output is correct
3	Correct	4 ms	856 KB	Output is correct
4	Correct	0 ms	468 KB	Output is correct
5	Correct	1 ms	600 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	376 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 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	3 ms	860 KB	Output is correct
17	Correct	32 ms	6236 KB	Output is correct
18	Correct	0 ms	344 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 #972430

Compilation message