oj.uz

Submission #217041

# Submission time Handle Problem Language Result Execution time Memory
217041 2020-03-28T18:23:59 Z sevlll Strange Device (APIO19_strange_device) C++17
35 / 100
 770 ms 49152 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) {
            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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 14 ms 1152 KB Output is correct
3 Correct 11 ms 1152 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 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 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 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 75 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 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 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 4 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 436 ms 49060 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 648 ms 49108 KB Output is correct
3 Correct 661 ms 49112 KB Output is correct
4 Correct 624 ms 48988 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 648 ms 49108 KB Output is correct
3 Correct 661 ms 49112 KB Output is correct
4 Correct 624 ms 48988 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 674 ms 48980 KB Output is correct
7 Correct 624 ms 48984 KB Output is correct
8 Correct 638 ms 49092 KB Output is correct
9 Correct 737 ms 49108 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 648 ms 49108 KB Output is correct
3 Correct 661 ms 49112 KB Output is correct
4 Correct 624 ms 48988 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 63 ms 6124 KB Output is correct
7 Correct 69 ms 6124 KB Output is correct
8 Correct 66 ms 6124 KB Output is correct
9 Correct 67 ms 6124 KB Output is correct
10 Correct 63 ms 6124 KB Output is correct
11 Correct 67 ms 6124 KB Output is correct
12 Correct 63 ms 6124 KB Output is correct
13 Correct 76 ms 6124 KB Output is correct
14 Correct 68 ms 6124 KB Output is correct
15 Correct 75 ms 6124 KB Output is correct
16 Correct 73 ms 6124 KB Output is correct
17 Correct 67 ms 6124 KB Output is correct
18 Correct 648 ms 49108 KB Output is correct
19 Correct 630 ms 48980 KB Output is correct
20 Correct 747 ms 48988 KB Output is correct
21 Correct 76 ms 6124 KB Output is correct
22 Correct 62 ms 6124 KB Output is correct
23 Correct 192 ms 22296 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 70 ms 6124 KB Output is correct
3 Correct 75 ms 6256 KB Output is correct
4 Correct 770 ms 49056 KB Output is correct
5 Correct 74 ms 6124 KB Output is correct
6 Correct 72 ms 6124 KB Output is correct
7 Correct 73 ms 6124 KB Output is correct
8 Correct 72 ms 6124 KB Output is correct
9 Correct 70 ms 6124 KB Output is correct
10 Correct 75 ms 6124 KB Output is correct
11 Correct 73 ms 6124 KB Output is correct
12 Correct 63 ms 6124 KB Output is correct
13 Correct 76 ms 6124 KB Output is correct
14 Correct 739 ms 49152 KB Output is correct
15 Correct 73 ms 6124 KB Output is correct
16 Correct 609 ms 49068 KB Output is correct
17 Correct 623 ms 49040 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 14 ms 1152 KB Output is correct
3 Correct 11 ms 1152 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 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 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 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 75 ms 6124 KB Output is correct
18 Incorrect 5 ms 384 KB Output isn't correct