Submission #485562

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485562	2021-11-08T10:09:57 Z	dxz05	Strange Device (APIO19_strange_device)	C++14	35 / 100	642 ms	53200 KB

strange_device

#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.000001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e2;
const int M = 2222;

void solve(int TC) {
    int n; ll a, b;
    cin >> n >> a >> b;

    ll x = a / __gcd(a, b + 1) * b;

    vector<pair<ll, ll>> segments;
    for (int i = 1; i <= n; i++){
        ll l, r;
        cin >> l >> r;

        if (r - l + 1 >= x){
            cout << x << endl;
            return;
        }

        l %= x, r %= x;

        if (l > r){
            segments.emplace_back(l, x - 1);
            segments.emplace_back(0, r);
        } else segments.emplace_back(l, r);

    }

    sort(all(segments));

    ll ans = 0;
    n = segments.size();
    for (int i = 0; i < n;){
        ll l = segments[i].first, r = segments[i].second;
        int j = i;
        while (j < n && segments[j].first <= r){
            r = max(r, segments[j].second);
            j++;
        }

        ans += r - l + 1;

        i = j;
    }

    cout << ans;

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int TC = 1;
//    cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	5 ms	976 KB	Output is correct
3	Correct	5 ms	1016 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	312 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	5 ms	976 KB	Output is correct
17	Correct	51 ms	5708 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	312 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Incorrect	0 ms	204 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	330 ms	23888 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	391 ms	53136 KB	Output is correct
3	Correct	582 ms	26036 KB	Output is correct
4	Correct	428 ms	25316 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	391 ms	53136 KB	Output is correct
3	Correct	582 ms	26036 KB	Output is correct
4	Correct	428 ms	25316 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	495 ms	25176 KB	Output is correct
7	Correct	621 ms	25184 KB	Output is correct
8	Correct	523 ms	25280 KB	Output is correct
9	Correct	406 ms	53136 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	391 ms	53136 KB	Output is correct
3	Correct	582 ms	26036 KB	Output is correct
4	Correct	428 ms	25316 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	45 ms	5700 KB	Output is correct
7	Correct	45 ms	5688 KB	Output is correct
8	Correct	39 ms	5620 KB	Output is correct
9	Correct	39 ms	5688 KB	Output is correct
10	Correct	38 ms	5632 KB	Output is correct
11	Correct	47 ms	5692 KB	Output is correct
12	Correct	37 ms	5588 KB	Output is correct
13	Correct	53 ms	5648 KB	Output is correct
14	Correct	45 ms	5668 KB	Output is correct
15	Correct	44 ms	5696 KB	Output is correct
16	Correct	48 ms	5692 KB	Output is correct
17	Correct	37 ms	5660 KB	Output is correct
18	Correct	448 ms	25292 KB	Output is correct
19	Correct	496 ms	26024 KB	Output is correct
20	Correct	507 ms	26020 KB	Output is correct
21	Correct	40 ms	5608 KB	Output is correct
22	Correct	38 ms	5592 KB	Output is correct
23	Correct	122 ms	18412 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	39 ms	5604 KB	Output is correct
3	Correct	42 ms	5692 KB	Output is correct
4	Correct	528 ms	25896 KB	Output is correct
5	Correct	39 ms	5692 KB	Output is correct
6	Correct	38 ms	5692 KB	Output is correct
7	Correct	59 ms	5728 KB	Output is correct
8	Correct	39 ms	5636 KB	Output is correct
9	Correct	42 ms	5696 KB	Output is correct
10	Correct	45 ms	5604 KB	Output is correct
11	Correct	45 ms	5684 KB	Output is correct
12	Correct	34 ms	5688 KB	Output is correct
13	Correct	41 ms	5700 KB	Output is correct
14	Correct	642 ms	26012 KB	Output is correct
15	Correct	45 ms	5692 KB	Output is correct
16	Correct	425 ms	53200 KB	Output is correct
17	Correct	385 ms	53088 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	5 ms	976 KB	Output is correct
3	Correct	5 ms	1016 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	312 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	5 ms	976 KB	Output is correct
17	Correct	51 ms	5708 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct

Submission #485562

Compilation message