Submission #934537

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934537	2024-02-27T14:27:42 Z	ByeWorld	Strange Device (APIO19_strange_device)	C++14	35 / 100	1209 ms	48760 KB

strange_device

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define int long long
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int INF = 1e9+10;
const int MAXN = 1e6+10;

int n, a, b;
int F, K, P;
vector <pii> vec;
int ans;

signed main() {
	cin >> n >> a >> b;
	b++;
    F = __gcd(a, b);
    K = a/F * b;
    P = K - a/F;
    
    for(int i=1; i<=n; i++){
        int l, r; cin >> l >> r;
        if(r-l+1 >= P){
            cout << P << '\n'; exit(0);
        }
        l %= P; r %= P;
        if(l<=r){
            vec.pb({l, r});
        } else {
            vec.pb({l, P-1}); 
            vec.pb({0, r});
        }
    }
    sort(vec.begin(), vec.end());
    int las = -1, ans = 0;
    for(auto in : vec){
        if(in.se <= las) continue;
        ans += in.se - max(in.fi-1, las);
        las = in.se;
    }
    cout << ans << '\n';
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	10 ms	1116 KB	Output is correct
3	Correct	10 ms	1012 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	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 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	1 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	10 ms	1116 KB	Output is correct
17	Correct	102 ms	4944 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	2 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	678 ms	35340 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	988 ms	44804 KB	Output is correct
3	Correct	979 ms	44360 KB	Output is correct
4	Correct	981 ms	44468 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	988 ms	44804 KB	Output is correct
3	Correct	979 ms	44360 KB	Output is correct
4	Correct	981 ms	44468 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1209 ms	44384 KB	Output is correct
7	Correct	979 ms	48268 KB	Output is correct
8	Correct	1010 ms	48760 KB	Output is correct
9	Correct	1091 ms	48732 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	988 ms	44804 KB	Output is correct
3	Correct	979 ms	44360 KB	Output is correct
4	Correct	981 ms	44468 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	114 ms	5640 KB	Output is correct
7	Correct	113 ms	5568 KB	Output is correct
8	Correct	108 ms	5488 KB	Output is correct
9	Correct	102 ms	5608 KB	Output is correct
10	Correct	112 ms	5760 KB	Output is correct
11	Correct	99 ms	5572 KB	Output is correct
12	Correct	110 ms	5464 KB	Output is correct
13	Correct	106 ms	5680 KB	Output is correct
14	Correct	116 ms	5668 KB	Output is correct
15	Correct	103 ms	5672 KB	Output is correct
16	Correct	110 ms	5532 KB	Output is correct
17	Correct	107 ms	5536 KB	Output is correct
18	Correct	1000 ms	44304 KB	Output is correct
19	Correct	1025 ms	44168 KB	Output is correct
20	Correct	1041 ms	44812 KB	Output is correct
21	Correct	102 ms	5064 KB	Output is correct
22	Correct	99 ms	5084 KB	Output is correct
23	Correct	336 ms	19616 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	100 ms	5088 KB	Output is correct
3	Correct	123 ms	5056 KB	Output is correct
4	Correct	1105 ms	44176 KB	Output is correct
5	Correct	112 ms	5432 KB	Output is correct
6	Correct	124 ms	5000 KB	Output is correct
7	Correct	111 ms	5056 KB	Output is correct
8	Correct	101 ms	5124 KB	Output is correct
9	Correct	105 ms	5084 KB	Output is correct
10	Correct	103 ms	5152 KB	Output is correct
11	Correct	114 ms	4992 KB	Output is correct
12	Correct	108 ms	5164 KB	Output is correct
13	Correct	106 ms	5152 KB	Output is correct
14	Correct	1037 ms	45016 KB	Output is correct
15	Correct	118 ms	5076 KB	Output is correct
16	Correct	1014 ms	44248 KB	Output is correct
17	Correct	980 ms	44296 KB	Output is correct
18	Incorrect	1 ms	344 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	344 KB	Output is correct
2	Correct	10 ms	1116 KB	Output is correct
3	Correct	10 ms	1012 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	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 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	1 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	10 ms	1116 KB	Output is correct
17	Correct	102 ms	4944 KB	Output is correct
18	Incorrect	0 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #934537

Compilation message