oj.uz

Submission #217040

# Submission time Handle Problem Language Result Execution time Memory
217040 2020-03-28T18:22:13 Z sevlll Strange Device (APIO19_strange_device) C++17
65 / 100
 794 ms 53124 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;
    int num = a * b;
    vector<pair<int, int>> ev;
    for (auto p : pr) {
        int l = p.first, r = p.second;
        //if (r - l >= num - 1) {
        ////////    cout << 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;
        int type = p.second;
        if (bal) {
            ans += (x - last);
        }
        last = x;
        bal += type;
    }
    cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 11 ms 1536 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 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 14 ms 1536 KB Output is correct
17 Correct 78 ms 9836 KB Output is correct
18 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 433 ms 50388 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 625 ms 52312 KB Output is correct
3 Correct 673 ms 52180 KB Output is correct
4 Correct 635 ms 52276 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 625 ms 52312 KB Output is correct
3 Correct 673 ms 52180 KB Output is correct
4 Correct 635 ms 52276 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 656 ms 52276 KB Output is correct
7 Correct 623 ms 52188 KB Output is correct
8 Correct 620 ms 52180 KB Output is correct
9 Correct 755 ms 52164 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 625 ms 52312 KB Output is correct
3 Correct 673 ms 52180 KB Output is correct
4 Correct 635 ms 52276 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 71 ms 9964 KB Output is correct
7 Correct 69 ms 9836 KB Output is correct
8 Correct 66 ms 9840 KB Output is correct
9 Correct 66 ms 9836 KB Output is correct
10 Correct 71 ms 9836 KB Output is correct
11 Correct 66 ms 9836 KB Output is correct
12 Correct 62 ms 9868 KB Output is correct
13 Correct 75 ms 9864 KB Output is correct
14 Correct 64 ms 9840 KB Output is correct
15 Correct 79 ms 9836 KB Output is correct
16 Correct 75 ms 9836 KB Output is correct
17 Correct 69 ms 9836 KB Output is correct
18 Correct 657 ms 51424 KB Output is correct
19 Correct 614 ms 53124 KB Output is correct
20 Correct 763 ms 52932 KB Output is correct
21 Correct 74 ms 9836 KB Output is correct
22 Correct 59 ms 9836 KB Output is correct
23 Correct 188 ms 26212 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 75 ms 9864 KB Output is correct
3 Correct 72 ms 9840 KB Output is correct
4 Correct 794 ms 52276 KB Output is correct
5 Correct 74 ms 9836 KB Output is correct
6 Correct 77 ms 9964 KB Output is correct
7 Correct 73 ms 9836 KB Output is correct
8 Correct 75 ms 9840 KB Output is correct
9 Correct 72 ms 9836 KB Output is correct
10 Correct 76 ms 9868 KB Output is correct
11 Correct 79 ms 9964 KB Output is correct
12 Correct 66 ms 9836 KB Output is correct
13 Correct 74 ms 9836 KB Output is correct
14 Correct 743 ms 52232 KB Output is correct
15 Correct 79 ms 9836 KB Output is correct
16 Correct 601 ms 52052 KB Output is correct
17 Correct 645 ms 52696 KB Output is correct
18 Correct 4 ms 384 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 11 ms 1536 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 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 14 ms 1536 KB Output is correct
17 Correct 78 ms 9836 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Incorrect 5 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -