oj.uz

Submission #145367

# Submission time Handle Problem Language Result Execution time Memory
145367 2019-08-19T17:35:43 Z dolphingarlic Strange Device (APIO19_strange_device) C++14
35 / 100
 1016 ms 68212 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
typedef long long ll;
using namespace std;

// Observation: pairs are periodic, period = B * (A / gcd(A, B + 1))
// We can thus "line sweep" i.e. keep a vector of events and +1 for add,
// -1 for remove and count as long as positive

ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, a, b;
    cin >> n >> a >> b;
    ll period = b * (a / gcd(a, b + 1));
    vector<pair<ll, int>> events;
    FOR(i, 0, n) {
        ll x, y;
        cin >> x >> y;
        x += period - 1;
        y += period - 1;
        if (y - x >= period) {
            return cout << period << '\n', 0;
        }
        if (x % period > y % period) {
            events.push_back(make_pair(1, 0));
            events.push_back(make_pair(y % period + 1, 1));
            events.push_back(make_pair(x % period + 1, 0));
            events.push_back(make_pair(period, 1));
        } else {
            events.push_back(make_pair(x % period + 1, 0));
            events.push_back(make_pair(y % period + 1, 1));
        }
    }
    sort(events.begin(), events.end());
    ll cnt = 0, leftmost = -1, ans = 0;
    for (auto& i : events) {
        if (!i.second) {
            cnt++;
            if (leftmost == -1) leftmost = i.first;
        } else {
            cnt--;
            if (cnt == 0) {
                ans += (i.first - leftmost + 1);
                leftmost = -1;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 10 ms 1396 KB Output is correct
3 Correct 10 ms 1332 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 10 ms 1272 KB Output is correct
17 Correct 88 ms 6220 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 696 ms 68212 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 757 ms 35628 KB Output is correct
3 Correct 802 ms 34476 KB Output is correct
4 Correct 774 ms 34376 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 757 ms 35628 KB Output is correct
3 Correct 802 ms 34476 KB Output is correct
4 Correct 774 ms 34376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 780 ms 34532 KB Output is correct
7 Correct 767 ms 34356 KB Output is correct
8 Correct 758 ms 34540 KB Output is correct
9 Correct 859 ms 34476 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 757 ms 35628 KB Output is correct
3 Correct 802 ms 34476 KB Output is correct
4 Correct 774 ms 34376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 75 ms 6252 KB Output is correct
7 Correct 79 ms 6336 KB Output is correct
8 Correct 77 ms 6256 KB Output is correct
9 Correct 78 ms 6248 KB Output is correct
10 Correct 73 ms 6252 KB Output is correct
11 Correct 78 ms 6248 KB Output is correct
12 Correct 74 ms 6368 KB Output is correct
13 Correct 85 ms 6400 KB Output is correct
14 Correct 75 ms 6248 KB Output is correct
15 Correct 87 ms 6284 KB Output is correct
16 Correct 85 ms 6292 KB Output is correct
17 Correct 78 ms 6248 KB Output is correct
18 Correct 783 ms 34896 KB Output is correct
19 Correct 736 ms 34972 KB Output is correct
20 Correct 884 ms 35124 KB Output is correct
21 Correct 87 ms 6568 KB Output is correct
22 Correct 89 ms 6220 KB Output is correct
23 Correct 282 ms 35904 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 84 ms 6248 KB Output is correct
3 Correct 87 ms 5996 KB Output is correct
4 Correct 1016 ms 34604 KB Output is correct
5 Correct 84 ms 5964 KB Output is correct
6 Correct 84 ms 6088 KB Output is correct
7 Correct 84 ms 6016 KB Output is correct
8 Correct 85 ms 6272 KB Output is correct
9 Correct 81 ms 6240 KB Output is correct
10 Correct 124 ms 6240 KB Output is correct
11 Correct 84 ms 6368 KB Output is correct
12 Correct 77 ms 6268 KB Output is correct
13 Correct 86 ms 6248 KB Output is correct
14 Correct 854 ms 34888 KB Output is correct
15 Correct 86 ms 6496 KB Output is correct
16 Correct 723 ms 35492 KB Output is correct
17 Correct 763 ms 35376 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 10 ms 1396 KB Output is correct
3 Correct 10 ms 1332 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 10 ms 1272 KB Output is correct
17 Correct 88 ms 6220 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct