Submission #1003728

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1003728	2024-06-20T16:26:22 Z	underwaterkillerwhale	Strange Device (APIO19_strange_device)	C++17	65 / 100	288 ms	53340 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; {
        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	0 ms	344 KB	Output is correct
2	Correct	3 ms	860 KB	Output is correct
3	Correct	3 ms	860 KB	Output is correct
4	Correct	0 ms	360 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	352 KB	Output is correct
10	Correct	1 ms	356 KB	Output is correct
11	Correct	0 ms	472 KB	Output is correct
12	Correct	0 ms	356 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	840 KB	Output is correct
17	Correct	29 ms	6228 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	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	352 KB	Output is correct
4	Correct	0 ms	352 KB	Output is correct
5	Correct	178 ms	41328 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	266 ms	53052 KB	Output is correct
3	Correct	255 ms	53076 KB	Output is correct
4	Correct	272 ms	53340 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	266 ms	53052 KB	Output is correct
3	Correct	255 ms	53076 KB	Output is correct
4	Correct	272 ms	53340 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	267 ms	53172 KB	Output is correct
7	Correct	249 ms	53072 KB	Output is correct
8	Correct	239 ms	53072 KB	Output is correct
9	Correct	288 ms	53084 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	266 ms	53052 KB	Output is correct
3	Correct	255 ms	53076 KB	Output is correct
4	Correct	272 ms	53340 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	27 ms	6384 KB	Output is correct
7	Correct	29 ms	5524 KB	Output is correct
8	Correct	24 ms	6224 KB	Output is correct
9	Correct	27 ms	5712 KB	Output is correct
10	Correct	27 ms	5712 KB	Output is correct
11	Correct	27 ms	5724 KB	Output is correct
12	Correct	28 ms	5716 KB	Output is correct
13	Correct	28 ms	5716 KB	Output is correct
14	Correct	26 ms	5712 KB	Output is correct
15	Correct	29 ms	5724 KB	Output is correct
16	Correct	29 ms	5636 KB	Output is correct
17	Correct	27 ms	5748 KB	Output is correct
18	Correct	285 ms	53328 KB	Output is correct
19	Correct	233 ms	53072 KB	Output is correct
20	Correct	271 ms	53076 KB	Output is correct
21	Correct	28 ms	5720 KB	Output is correct
22	Correct	24 ms	5636 KB	Output is correct
23	Correct	105 ms	18148 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	30 ms	5724 KB	Output is correct
3	Correct	27 ms	6232 KB	Output is correct
4	Correct	286 ms	53216 KB	Output is correct
5	Correct	27 ms	5716 KB	Output is correct
6	Correct	28 ms	6252 KB	Output is correct
7	Correct	26 ms	5724 KB	Output is correct
8	Correct	29 ms	5712 KB	Output is correct
9	Correct	28 ms	5656 KB	Output is correct
10	Correct	29 ms	5724 KB	Output is correct
11	Correct	28 ms	5712 KB	Output is correct
12	Correct	29 ms	5724 KB	Output is correct
13	Correct	28 ms	5752 KB	Output is correct
14	Correct	275 ms	53048 KB	Output is correct
15	Correct	30 ms	5980 KB	Output is correct
16	Correct	254 ms	53076 KB	Output is correct
17	Correct	235 ms	53072 KB	Output is correct
18	Correct	0 ms	348 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	860 KB	Output is correct
4	Correct	0 ms	360 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	352 KB	Output is correct
10	Correct	1 ms	356 KB	Output is correct
11	Correct	0 ms	472 KB	Output is correct
12	Correct	0 ms	356 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	840 KB	Output is correct
17	Correct	29 ms	6228 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 #1003728

Compilation message