Submission #782592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
782592	2023-07-14T06:16:55 Z	christinelynn	Strange Device (APIO19_strange_device)	C++17	35 / 100	354 ms	18072 KB

strange_device

# include <bits/stdc++.h>
# define int long long
# define vi vector<int>
# define pb push_back
# define pii pair<int, int>
# define fi first
# define se second
# define endl '\n'
# define jess ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n, a, b;

void solve() {
    cin >> n >> a >> b;
    __int128_t t=(__int128_t)a*b;
    int cycle=t / __gcd(a, b+1);
    vector<pii> v;
    for(int i=1; i<=n; i++) {
        int l, r;
        cin >> l >> r;
        if((r-l+1) >= cycle) {
            cout << cycle << endl;
            return;
        }
        l%=cycle;
        r%=cycle;
        if(r < l) {
            v.pb({l, cycle-1});
            v.pb({0, r});
        } else {
            v.pb({l, r});
        }
    }
    sort(v.begin(), v.end());
    bool st=1;
    int l=0, r=1, ans=0;
    // for(pii i : v) cout << "l r " << i.fi << " " << i.se << endl;
    for(auto i : v) {
        if(st) {
            l=i.fi, r=i.se;
            st=0;
            continue;
        }
        if(i.fi>=l && i.fi<=r) {
            r=max(r, i.se);
        } else {
            ans+=(r-l+1);
            l=i.fi, r=i.se;
        }
    }
    ans+=(r-l+1);
    cout << ans << endl;
}
 
signed main() {
    jess;
    solve();
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	4 ms	948 KB	Output is correct
3	Correct	4 ms	948 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 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	316 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	320 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	4 ms	856 KB	Output is correct
17	Correct	35 ms	2916 KB	Output is correct
18	Incorrect	1 ms	340 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	0 ms	212 KB	Output is correct
4	Correct	0 ms	320 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	225 ms	17040 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	305 ms	17012 KB	Output is correct
3	Correct	315 ms	17848 KB	Output is correct
4	Correct	313 ms	17836 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	305 ms	17012 KB	Output is correct
3	Correct	315 ms	17848 KB	Output is correct
4	Correct	313 ms	17836 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	321 ms	17764 KB	Output is correct
7	Correct	331 ms	17708 KB	Output is correct
8	Correct	317 ms	17532 KB	Output is correct
9	Correct	334 ms	17456 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	305 ms	17012 KB	Output is correct
3	Correct	315 ms	17848 KB	Output is correct
4	Correct	313 ms	17836 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	31 ms	3040 KB	Output is correct
7	Correct	33 ms	3124 KB	Output is correct
8	Correct	33 ms	3096 KB	Output is correct
9	Correct	32 ms	3104 KB	Output is correct
10	Correct	32 ms	2984 KB	Output is correct
11	Correct	33 ms	3104 KB	Output is correct
12	Correct	31 ms	3096 KB	Output is correct
13	Correct	33 ms	3120 KB	Output is correct
14	Correct	31 ms	3100 KB	Output is correct
15	Correct	36 ms	3144 KB	Output is correct
16	Correct	34 ms	3040 KB	Output is correct
17	Correct	32 ms	3136 KB	Output is correct
18	Correct	336 ms	17820 KB	Output is correct
19	Correct	348 ms	17476 KB	Output is correct
20	Correct	337 ms	18072 KB	Output is correct
21	Correct	34 ms	3276 KB	Output is correct
22	Correct	30 ms	3116 KB	Output is correct
23	Correct	102 ms	9732 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	41 ms	3240 KB	Output is correct
3	Correct	34 ms	3108 KB	Output is correct
4	Correct	354 ms	17604 KB	Output is correct
5	Correct	42 ms	3020 KB	Output is correct
6	Correct	34 ms	2996 KB	Output is correct
7	Correct	35 ms	3108 KB	Output is correct
8	Correct	35 ms	3016 KB	Output is correct
9	Correct	38 ms	3132 KB	Output is correct
10	Correct	36 ms	3100 KB	Output is correct
11	Correct	38 ms	3072 KB	Output is correct
12	Correct	37 ms	3128 KB	Output is correct
13	Correct	38 ms	3136 KB	Output is correct
14	Correct	332 ms	17516 KB	Output is correct
15	Correct	34 ms	3064 KB	Output is correct
16	Correct	317 ms	17360 KB	Output is correct
17	Correct	308 ms	17972 KB	Output is correct
18	Incorrect	1 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	1 ms	212 KB	Output is correct
2	Correct	4 ms	948 KB	Output is correct
3	Correct	4 ms	948 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 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	316 KB	Output is correct
10	Correct	1 ms	320 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	320 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	4 ms	856 KB	Output is correct
17	Correct	35 ms	2916 KB	Output is correct
18	Incorrect	1 ms	340 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #782592

Compilation message