oj.uz

Submission #217007

# Submission time Handle Problem Language Result Execution time Memory
217007 2020-03-28T17:37:10 Z sevlll Strange Device (APIO19_strange_device) C++14
65 / 100
 856 ms 50900 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;
    if (a * b >= 1e18+8800) {
        int ans = 0;
        for (auto p : pr) {
            ans += p.second - p.first+1;
        }
        cout << ans;
        return 0;
    }
    int num = a * b;
    vector<pair<int, int>> ev;
    for (auto p : pr) {
        int l = p.first, r = p.second;
        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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 14 ms 1664 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 5 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 5 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 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 11 ms 1536 KB Output is correct
17 Correct 76 ms 8172 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 435 ms 49748 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 645 ms 50516 KB Output is correct
3 Correct 646 ms 50524 KB Output is correct
4 Correct 626 ms 50524 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 645 ms 50516 KB Output is correct
3 Correct 646 ms 50524 KB Output is correct
4 Correct 626 ms 50524 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 657 ms 50424 KB Output is correct
7 Correct 653 ms 50516 KB Output is correct
8 Correct 856 ms 50416 KB Output is correct
9 Correct 763 ms 50520 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 645 ms 50516 KB Output is correct
3 Correct 646 ms 50524 KB Output is correct
4 Correct 626 ms 50524 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 63 ms 9836 KB Output is correct
7 Correct 72 ms 9836 KB Output is correct
8 Correct 86 ms 9836 KB Output is correct
9 Correct 68 ms 9836 KB Output is correct
10 Correct 63 ms 9836 KB Output is correct
11 Correct 65 ms 9836 KB Output is correct
12 Correct 66 ms 9836 KB Output is correct
13 Correct 73 ms 9836 KB Output is correct
14 Correct 67 ms 9836 KB Output is correct
15 Correct 76 ms 9836 KB Output is correct
16 Correct 76 ms 9836 KB Output is correct
17 Correct 66 ms 9840 KB Output is correct
18 Correct 664 ms 50408 KB Output is correct
19 Correct 631 ms 50768 KB Output is correct
20 Correct 773 ms 50772 KB Output is correct
21 Correct 77 ms 9836 KB Output is correct
22 Correct 62 ms 9836 KB Output is correct
23 Correct 195 ms 34920 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 72 ms 9836 KB Output is correct
3 Correct 72 ms 9836 KB Output is correct
4 Correct 799 ms 50528 KB Output is correct
5 Correct 73 ms 9836 KB Output is correct
6 Correct 73 ms 9836 KB Output is correct
7 Correct 83 ms 9964 KB Output is correct
8 Correct 75 ms 9836 KB Output is correct
9 Correct 73 ms 9836 KB Output is correct
10 Correct 74 ms 9836 KB Output is correct
11 Correct 74 ms 9836 KB Output is correct
12 Correct 68 ms 9868 KB Output is correct
13 Correct 81 ms 9836 KB Output is correct
14 Correct 732 ms 50524 KB Output is correct
15 Correct 76 ms 9840 KB Output is correct
16 Correct 599 ms 50500 KB Output is correct
17 Correct 653 ms 50900 KB Output is correct
18 Correct 5 ms 384 KB Output is 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 1664 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 5 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 5 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 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 11 ms 1536 KB Output is correct
17 Correct 76 ms 8172 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 -