Submission #1003731

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1003731	2024-06-20T16:29:00 Z	underwaterkillerwhale	Strange Device (APIO19_strange_device)	C++17	65 / 100	354 ms	53208 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 = 2e18 + 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 = min((__int128)INF, (__int128)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	0 ms	344 KB	Output is correct
2	Correct	3 ms	860 KB	Output is correct
3	Correct	3 ms	844 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	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	468 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	356 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	31 ms	5504 KB	Output is correct
18	Correct	0 ms	352 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	360 KB	Output is correct
2	Incorrect	356 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	348 KB	Output is correct
2	Correct	0 ms	512 KB	Output is correct
3	Correct	0 ms	352 KB	Output is correct
4	Correct	0 ms	352 KB	Output is correct
5	Correct	176 ms	41132 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	273 ms	53180 KB	Output is correct
3	Correct	257 ms	53020 KB	Output is correct
4	Correct	256 ms	53120 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	273 ms	53180 KB	Output is correct
3	Correct	257 ms	53020 KB	Output is correct
4	Correct	256 ms	53120 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	240 ms	53036 KB	Output is correct
7	Correct	252 ms	53000 KB	Output is correct
8	Correct	287 ms	52952 KB	Output is correct
9	Correct	332 ms	53208 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	273 ms	53180 KB	Output is correct
3	Correct	257 ms	53020 KB	Output is correct
4	Correct	256 ms	53120 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	26 ms	5744 KB	Output is correct
7	Correct	29 ms	5716 KB	Output is correct
8	Correct	29 ms	5712 KB	Output is correct
9	Correct	26 ms	5560 KB	Output is correct
10	Correct	27 ms	5716 KB	Output is correct
11	Correct	24 ms	5720 KB	Output is correct
12	Correct	24 ms	5716 KB	Output is correct
13	Correct	28 ms	5724 KB	Output is correct
14	Correct	24 ms	5712 KB	Output is correct
15	Correct	36 ms	5712 KB	Output is correct
16	Correct	32 ms	5704 KB	Output is correct
17	Correct	31 ms	5720 KB	Output is correct
18	Correct	293 ms	53072 KB	Output is correct
19	Correct	266 ms	53196 KB	Output is correct
20	Correct	354 ms	52964 KB	Output is correct
21	Correct	28 ms	5664 KB	Output is correct
22	Correct	29 ms	5720 KB	Output is correct
23	Correct	79 ms	18272 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	29 ms	5592 KB	Output is correct
3	Correct	38 ms	5696 KB	Output is correct
4	Correct	296 ms	53180 KB	Output is correct
5	Correct	29 ms	5712 KB	Output is correct
6	Correct	36 ms	5520 KB	Output is correct
7	Correct	36 ms	5720 KB	Output is correct
8	Correct	30 ms	5720 KB	Output is correct
9	Correct	37 ms	5724 KB	Output is correct
10	Correct	27 ms	5716 KB	Output is correct
11	Correct	32 ms	5724 KB	Output is correct
12	Correct	27 ms	5720 KB	Output is correct
13	Correct	28 ms	5640 KB	Output is correct
14	Correct	260 ms	52288 KB	Output is correct
15	Correct	26 ms	5512 KB	Output is correct
16	Correct	233 ms	52308 KB	Output is correct
17	Correct	265 ms	52216 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	0 ms	344 KB	Output is correct
2	Correct	3 ms	860 KB	Output is correct
3	Correct	3 ms	844 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	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	468 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	356 KB	Output is correct
16	Correct	3 ms	860 KB	Output is correct
17	Correct	31 ms	5504 KB	Output is correct
18	Correct	0 ms	352 KB	Output is correct
19	Correct	0 ms	360 KB	Output is correct
20	Incorrect	0 ms	356 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #1003731

Compilation message