oj.uz

Submission #217014

# Submission time Handle Problem Language Result Execution time Memory
217014 2020-03-28T17:48:13 Z sevlll Strange Device (APIO19_strange_device) C++17
35 / 100
 794 ms 49116 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>

#define pb push_back
#define int long long
#define str string
using namespace std;
const int M = 1e9 + 7;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, a, b;
    cin >> n >> a >> b;
    vector<pair<int, int>> pr(n);
    for (int i = 0; i < n; i++) cin >> pr[i].first >> pr[i].second;
    int g = gcd(a, b + 1);
    a /= g;
    __int128_t num = a * b;
    vector<pair<int, int>> ev;
    for (auto p : pr) {
        int l = p.first, r = p.second;
        if (r - l + 1 >= num) {
            cout << (int) num;
            return 0;
        }
        l %= num;
        r %= num;
        if (r < l) {
            ev.pb({l, 1});
            ev.pb({num, -1});
            ev.pb({0, 1});
            ev.pb({r + 1, -1});
        } else {
            ev.pb({l, 1});
            ev.pb({r + 1, -1});
        }
    }
    sort(ev.begin(), ev.end());
    int bal = 0;
    int last = 0;
    int ans = 0;
    for (auto p : ev) {
        int x = p.first, type = p.second;
        if (bal) {
            ans += (x - last);
        }
        last = x;
        bal += type;
    }
    cout << ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 11 ms 1152 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 11 ms 1152 KB Output is correct
17 Correct 76 ms 6124 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 463 ms 49044 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 638 ms 48984 KB Output is correct
3 Correct 667 ms 48980 KB Output is correct
4 Correct 632 ms 49076 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 638 ms 48984 KB Output is correct
3 Correct 667 ms 48980 KB Output is correct
4 Correct 632 ms 49076 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 673 ms 49112 KB Output is correct
7 Correct 654 ms 49044 KB Output is correct
8 Correct 664 ms 49012 KB Output is correct
9 Correct 736 ms 48988 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 638 ms 48984 KB Output is correct
3 Correct 667 ms 48980 KB Output is correct
4 Correct 632 ms 49076 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 66 ms 6124 KB Output is correct
7 Correct 67 ms 6124 KB Output is correct
8 Correct 64 ms 6124 KB Output is correct
9 Correct 71 ms 6124 KB Output is correct
10 Correct 62 ms 6132 KB Output is correct
11 Correct 65 ms 6124 KB Output is correct
12 Correct 63 ms 6176 KB Output is correct
13 Correct 70 ms 6124 KB Output is correct
14 Correct 65 ms 6124 KB Output is correct
15 Correct 77 ms 6124 KB Output is correct
16 Correct 79 ms 6252 KB Output is correct
17 Correct 69 ms 6124 KB Output is correct
18 Correct 673 ms 48992 KB Output is correct
19 Correct 620 ms 48992 KB Output is correct
20 Correct 787 ms 49116 KB Output is correct
21 Correct 77 ms 6124 KB Output is correct
22 Correct 61 ms 6124 KB Output is correct
23 Correct 191 ms 22244 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 74 ms 6124 KB Output is correct
3 Correct 72 ms 6124 KB Output is correct
4 Correct 794 ms 49108 KB Output is correct
5 Correct 72 ms 6124 KB Output is correct
6 Correct 72 ms 6124 KB Output is correct
7 Correct 72 ms 6128 KB Output is correct
8 Correct 77 ms 6124 KB Output is correct
9 Correct 72 ms 6124 KB Output is correct
10 Correct 74 ms 6124 KB Output is correct
11 Correct 74 ms 6124 KB Output is correct
12 Correct 67 ms 6124 KB Output is correct
13 Correct 75 ms 6132 KB Output is correct
14 Correct 756 ms 48980 KB Output is correct
15 Correct 76 ms 6124 KB Output is correct
16 Correct 611 ms 48980 KB Output is correct
17 Correct 632 ms 48980 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 11 ms 1152 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 11 ms 1152 KB Output is correct
17 Correct 76 ms 6124 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct