Submission #972447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
972447	2024-04-30T12:37:49 Z	simona1230	Strange Device (APIO19_strange_device)	C++17	65 / 100	346 ms	36392 KB

strange_device

#include <bits/stdc++.h>

using namespace std;
long long n,a,b;
map<pair<long long,long long>,long long> mp;
pair<long long,long long> p[2000001];
void solve()
{
    int cnt=n;
    long long h=1e18;
    a/=__gcd(a,b+1);
    if(1e18/a>b)h=b*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	356 KB	Output is correct
2	Correct	4 ms	860 KB	Output is correct
3	Correct	4 ms	848 KB	Output is correct
4	Correct	1 ms	476 KB	Output is correct
5	Correct	0 ms	352 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	356 KB	Output is correct
8	Correct	0 ms	356 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	352 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	0 ms	352 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	4 ms	840 KB	Output is correct
17	Correct	36 ms	5224 KB	Output is correct
18	Correct	0 ms	464 KB	Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	356 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	233 ms	30352 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	307 ms	36240 KB	Output is correct
3	Correct	292 ms	36068 KB	Output is correct
4	Correct	302 ms	36392 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	307 ms	36240 KB	Output is correct
3	Correct	292 ms	36068 KB	Output is correct
4	Correct	302 ms	36392 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	303 ms	36116 KB	Output is correct
7	Correct	287 ms	36064 KB	Output is correct
8	Correct	281 ms	36352 KB	Output is correct
9	Correct	309 ms	36228 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	307 ms	36240 KB	Output is correct
3	Correct	292 ms	36068 KB	Output is correct
4	Correct	302 ms	36392 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	32 ms	4944 KB	Output is correct
7	Correct	31 ms	4948 KB	Output is correct
8	Correct	28 ms	4904 KB	Output is correct
9	Correct	29 ms	4944 KB	Output is correct
10	Correct	30 ms	4980 KB	Output is correct
11	Correct	32 ms	4796 KB	Output is correct
12	Correct	28 ms	4772 KB	Output is correct
13	Correct	34 ms	4992 KB	Output is correct
14	Correct	29 ms	4784 KB	Output is correct
15	Correct	33 ms	4796 KB	Output is correct
16	Correct	32 ms	4836 KB	Output is correct
17	Correct	30 ms	4948 KB	Output is correct
18	Correct	291 ms	36176 KB	Output is correct
19	Correct	277 ms	36236 KB	Output is correct
20	Correct	329 ms	36236 KB	Output is correct
21	Correct	32 ms	4948 KB	Output is correct
22	Correct	28 ms	4872 KB	Output is correct
23	Correct	85 ms	13464 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	34 ms	5256 KB	Output is correct
3	Correct	32 ms	4896 KB	Output is correct
4	Correct	346 ms	36176 KB	Output is correct
5	Correct	37 ms	4808 KB	Output is correct
6	Correct	41 ms	4904 KB	Output is correct
7	Correct	31 ms	4832 KB	Output is correct
8	Correct	32 ms	5164 KB	Output is correct
9	Correct	34 ms	4900 KB	Output is correct
10	Correct	34 ms	4852 KB	Output is correct
11	Correct	34 ms	4824 KB	Output is correct
12	Correct	30 ms	4944 KB	Output is correct
13	Correct	33 ms	4788 KB	Output is correct
14	Correct	326 ms	36280 KB	Output is correct
15	Correct	30 ms	4948 KB	Output is correct
16	Correct	289 ms	36236 KB	Output is correct
17	Correct	280 ms	36236 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	0 ms	356 KB	Output is correct
2	Correct	4 ms	860 KB	Output is correct
3	Correct	4 ms	848 KB	Output is correct
4	Correct	1 ms	476 KB	Output is correct
5	Correct	0 ms	352 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	356 KB	Output is correct
8	Correct	0 ms	356 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	352 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	0 ms	352 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	4 ms	840 KB	Output is correct
17	Correct	36 ms	5224 KB	Output is correct
18	Correct	0 ms	464 KB	Output is correct
19	Correct	0 ms	352 KB	Output is correct
20	Incorrect	0 ms	352 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #972447

Compilation message