Submission #1003711

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1003711	2024-06-20T16:02:11 Z	underwaterkillerwhale	Strange Device (APIO19_strange_device)	C++17	65 / 100	331 ms	53200 KB

strange_device

#ifdef ONLINE_JUDGE
    #include "cyberland.h"
#endif

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 1e6 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e18 + 7;
const int BASE = 137;

int n;
ll A, B;
pair<ll, ll> a[N];


void solution() {
    cin >> n >> A >> B;
    rep (i ,1, n) {
        cin >> a[i].fs >> a[i].se;
    }
    ll K; {
        if (A / __gcd (A, B + 1) > INF / B)
            K = INF;
        else K = A / __gcd(A, B + 1) * B;
    }
    rep (i, 1, n) {
        a[i].fs %= K;
        a[i].se %= K;
        if (a[i].se < a[i].fs) {
            a[++n] = {0, a[i].se};
            a[i].se = K - 1;
        }
    }
    sort (a +1 , a + 1 + n);
    ll mnL = a[1].fs, mxR = a[1].se;
    ll res = 0;
    rep (i, 2, n) {
        if (a[i].fs > mxR) {
            res += mxR - mnL + 1;
            mnL = a[i].fs;
            mxR = a[i].se;
        }
        else {
            mxR = max(mxR, a[i].se);
        }
    }
    res += mxR - mnL + 1;
    cout << res <<"\n";

}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    file ("c");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}

/*
7
1 2 3 1 2 1 3
1
4 4 30
3
1 1 2 1
0 1 5
0 2 5
1 3 2
2 3 4


3 2
0 1 5
0 2 5
1
1 2

*/

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	3 ms	992 KB	Output is correct
3	Correct	3 ms	880 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	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 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	996 KB	Output is correct
17	Correct	29 ms	5552 KB	Output is correct
18	Correct	0 ms	348 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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	476 KB	Output is correct
5	Correct	183 ms	41148 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	285 ms	52780 KB	Output is correct
3	Correct	277 ms	52772 KB	Output is correct
4	Correct	279 ms	52820 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	285 ms	52780 KB	Output is correct
3	Correct	277 ms	52772 KB	Output is correct
4	Correct	279 ms	52820 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	273 ms	53136 KB	Output is correct
7	Correct	236 ms	52820 KB	Output is correct
8	Correct	249 ms	52820 KB	Output is correct
9	Correct	264 ms	52820 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	285 ms	52780 KB	Output is correct
3	Correct	277 ms	52772 KB	Output is correct
4	Correct	279 ms	52820 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	24 ms	5720 KB	Output is correct
7	Correct	28 ms	5616 KB	Output is correct
8	Correct	22 ms	5712 KB	Output is correct
9	Correct	28 ms	5724 KB	Output is correct
10	Correct	26 ms	5716 KB	Output is correct
11	Correct	26 ms	5516 KB	Output is correct
12	Correct	24 ms	5580 KB	Output is correct
13	Correct	30 ms	5480 KB	Output is correct
14	Correct	32 ms	5712 KB	Output is correct
15	Correct	27 ms	5720 KB	Output is correct
16	Correct	27 ms	5664 KB	Output is correct
17	Correct	28 ms	5716 KB	Output is correct
18	Correct	248 ms	52812 KB	Output is correct
19	Correct	246 ms	53096 KB	Output is correct
20	Correct	287 ms	52820 KB	Output is correct
21	Correct	28 ms	5716 KB	Output is correct
22	Correct	22 ms	5596 KB	Output is correct
23	Correct	70 ms	18292 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	33 ms	5860 KB	Output is correct
3	Correct	28 ms	5736 KB	Output is correct
4	Correct	331 ms	53180 KB	Output is correct
5	Correct	28 ms	5712 KB	Output is correct
6	Correct	29 ms	5724 KB	Output is correct
7	Correct	28 ms	5724 KB	Output is correct
8	Correct	29 ms	5720 KB	Output is correct
9	Correct	24 ms	5716 KB	Output is correct
10	Correct	25 ms	5668 KB	Output is correct
11	Correct	26 ms	5640 KB	Output is correct
12	Correct	22 ms	5584 KB	Output is correct
13	Correct	28 ms	5712 KB	Output is correct
14	Correct	257 ms	53200 KB	Output is correct
15	Correct	25 ms	5584 KB	Output is correct
16	Correct	265 ms	53060 KB	Output is correct
17	Correct	229 ms	52896 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	3 ms	992 KB	Output is correct
3	Correct	3 ms	880 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	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 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	996 KB	Output is correct
17	Correct	29 ms	5552 KB	Output is correct
18	Correct	0 ms	348 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 #1003711

Compilation message