Submission #721465

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
721465	2023-04-11T02:04:22 Z	Darren0724	Strange Device (APIO19_strange_device)	C++17	35 / 100	436 ms	17956 KB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
const int INF=9e18;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;cin>>t;
    int a,b;cin>>a>>b;
    int m=0;
    int g=__gcd(a,b+1);
    __int128 tmp=a*b/g;
    if(tmp>INF){
        m=INF;
    }
    else{
        m=tmp;
    }
    vector<pair<int,int>> v;
    for(int i=0;i<t;i++){
        int l,r;cin>>l>>r;
        if(r-l+1>=m){
            cout<<m<<endl;
            return 0;
        }
        if(r%m<l%m){
            v.push_back({l%m,m-1});
            v.push_back({0,r%m});
        }
        else{
            v.push_back({l%m,r%m});
        }
    }
    sort(all(v));
    int ans=0;
    int l=0;
    for(pair<int,int> p:v){
        p.first=max(p.first,l);
        if(p.second<p.first){
            continue;
        }
        ans+=(p.second-p.first+1);
        l=p.second+1;
    }
    cout<<ans<<endl;


    return 0;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	4 ms	600 KB	Output is correct
3	Correct	4 ms	600 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	6 ms	688 KB	Output is correct
17	Correct	43 ms	2436 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	277 ms	16768 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	392 ms	17172 KB	Output is correct
3	Correct	369 ms	17196 KB	Output is correct
4	Correct	376 ms	17848 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	392 ms	17172 KB	Output is correct
3	Correct	369 ms	17196 KB	Output is correct
4	Correct	376 ms	17848 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	395 ms	17956 KB	Output is correct
7	Correct	388 ms	17652 KB	Output is correct
8	Correct	387 ms	17728 KB	Output is correct
9	Correct	432 ms	17428 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	392 ms	17172 KB	Output is correct
3	Correct	369 ms	17196 KB	Output is correct
4	Correct	376 ms	17848 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	36 ms	2400 KB	Output is correct
7	Correct	39 ms	2512 KB	Output is correct
8	Correct	35 ms	2468 KB	Output is correct
9	Correct	39 ms	2376 KB	Output is correct
10	Correct	39 ms	2512 KB	Output is correct
11	Correct	39 ms	2376 KB	Output is correct
12	Correct	37 ms	2504 KB	Output is correct
13	Correct	39 ms	2472 KB	Output is correct
14	Correct	37 ms	2500 KB	Output is correct
15	Correct	41 ms	2484 KB	Output is correct
16	Correct	39 ms	2412 KB	Output is correct
17	Correct	39 ms	2512 KB	Output is correct
18	Correct	409 ms	17696 KB	Output is correct
19	Correct	385 ms	17724 KB	Output is correct
20	Correct	423 ms	17580 KB	Output is correct
21	Correct	39 ms	2512 KB	Output is correct
22	Correct	35 ms	2376 KB	Output is correct
23	Correct	118 ms	8596 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	40 ms	2460 KB	Output is correct
3	Correct	45 ms	2512 KB	Output is correct
4	Correct	436 ms	16824 KB	Output is correct
5	Correct	47 ms	2512 KB	Output is correct
6	Correct	43 ms	2504 KB	Output is correct
7	Correct	44 ms	2396 KB	Output is correct
8	Correct	44 ms	2512 KB	Output is correct
9	Correct	42 ms	2504 KB	Output is correct
10	Correct	40 ms	2404 KB	Output is correct
11	Correct	40 ms	2400 KB	Output is correct
12	Correct	35 ms	2512 KB	Output is correct
13	Correct	40 ms	2512 KB	Output is correct
14	Correct	411 ms	16764 KB	Output is correct
15	Correct	39 ms	2512 KB	Output is correct
16	Correct	377 ms	16860 KB	Output is correct
17	Correct	366 ms	16872 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	4 ms	600 KB	Output is correct
3	Correct	4 ms	600 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	6 ms	688 KB	Output is correct
17	Correct	43 ms	2436 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #721465

Compilation message