oj.uz

답안 #527655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527655 2022-02-17T22:31:43 Z Olympia 이상한 기계 (APIO19_strange_device) C++17
100 / 100
 2196 ms 63540 KB 
#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
class Intervals {
public:
    set<pair<int64_t,int64_t>> intervals;
    void print () {
        for (auto& p: intervals) {
            cout << p.first << " " << p.second << '\n';
        }
        cout << '\n';
    }
    pair<int64_t,int64_t> leftIntersect (pair<int64_t,int64_t> &p) {
        auto it = intervals.upper_bound({p.first + 1, -1});
        if (it == intervals.begin()) {
            return {-1, -1};
        }
        it--;
        pair<int64_t,int64_t> q = *it;
        if (q.second < p.first) {
            return {-1, -1};
        }
        return q;
    }
    pair<int64_t,int64_t> rightIntersect (pair<int64_t,int64_t> p) {
        auto it = intervals.upper_bound({p.second + 1, -1});
        if (it == intervals.begin()) {
            return {-1, -1};
        }
        it--;
        pair<int64_t,int64_t> q = *it;
        if (q.first > p.second) {
            return {-1, -1};
        }
        if (q.first < p.first) {
            return {-1, -1};
        }
        return q;
    }
    bool willChange (pair<int64_t,int64_t> p) {
        pair<int64_t,int64_t> q = leftIntersect(p);
        if (q.first < 0 && q.second < 0) {
            return true;
        }
        if (q.first <= p.first && q.second >= p.second) {
            return false;
        }
        return true;
    }
    pair<int64_t,int64_t> update_left (pair<int64_t,int64_t> p) {
        pair<int64_t,int64_t> q = leftIntersect(p);
        if (q.first == -1 && q.second == -1) {
            return p;
        }
        if (q.second < p.first) {
            return p;
        }
        if (intervals.count(q)) intervals.erase(q);
        return {q.first, p.second};
    }
    pair<int64_t,int64_t> update_right (pair<int64_t,int64_t> p) {
        pair<int64_t,int64_t> q = rightIntersect(p);
        if (q.first == -1 && q.second == -1) {
            return p;
        }
        if (q.first > p.second) {
            return p;
        }
        if (intervals.count(q)) intervals.erase(q);
        return {p.first, q.second};
    }
    void erase_in_between (pair<int64_t,int64_t> p) {
        auto it = intervals.lower_bound({p.first, -1});
        set<pair<int64_t,int64_t>> to_erase;
        while (it != intervals.end()) {
            if ((*it).second < p.second) {
                to_erase.insert(*it);
            } else {
                break;
            }
            it++;
        }
        for (auto& q: to_erase) {
            intervals.erase(q);
        }
    }
    void add_interval (pair<int64_t,int64_t> p) {
        if (!willChange(p)) {
            return;
        }
        erase_in_between(p);
        pair<int64_t,int64_t> new_p1 = update_right(update_left(p));
        intervals.insert(new_p1);
    }
};
int64_t gcd (int64_t a, int64_t b) {
    if (!a || !b) return max(a,b);
    return gcd(max(a,b) % min(a,b), min(a,b));
}
int main () {
    int N;
    int64_t A, B;
    cin >> N >> A >> B;
    A /= gcd(A, B + 1);
    int64_t prod;
    if (A < 1e18/B) {
        prod = A * B;
    } else {
        prod = 1e18;
    }
    Intervals myInterval;
    for (int i = 0; i < N; i++) {
        int64_t x, y;
        cin >> x >> y;
        if (abs(y - x) >= prod) {
            myInterval.add_interval({0, prod - 1});
            continue;
        }
        x %= (prod), y %= (prod);
        if (x <= y) {
            myInterval.add_interval({x, y});
        } else {
            swap(x, y);
            myInterval.add_interval({0, x});
            myInterval.add_interval({y, prod - 1});
        }
    }
    int64_t ans = 0;
    for (auto& p: myInterval.intervals) {
        ans += p.second - p.first + 1;
    }
    cout << ans << '\n';
}

Compilation message

strange_device.cpp:15: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   15 | #pragma GCC optimization ("O3")
      | 
strange_device.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("Ofast")
      | 
strange_device.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 17 ms 844 KB Output is correct
3 Correct 16 ms 820 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 16 ms 844 KB Output is correct
17 Correct 178 ms 6420 KB Output is correct
18 Correct 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 857 ms 272 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1795 ms 62876 KB Output is correct
3 Correct 1875 ms 62864 KB Output is correct
4 Correct 2001 ms 62900 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1795 ms 62876 KB Output is correct
3 Correct 1875 ms 62864 KB Output is correct
4 Correct 2001 ms 62900 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1800 ms 63044 KB Output is correct
7 Correct 1892 ms 62800 KB Output is correct
8 Correct 1821 ms 62852 KB Output is correct
9 Correct 2017 ms 62888 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1795 ms 62876 KB Output is correct
3 Correct 1875 ms 62864 KB Output is correct
4 Correct 2001 ms 62900 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 156 ms 6376 KB Output is correct
7 Correct 158 ms 6380 KB Output is correct
8 Correct 160 ms 6420 KB Output is correct
9 Correct 181 ms 6716 KB Output is correct
10 Correct 163 ms 6448 KB Output is correct
11 Correct 162 ms 6516 KB Output is correct
12 Correct 176 ms 6484 KB Output is correct
13 Correct 208 ms 6516 KB Output is correct
14 Correct 167 ms 6468 KB Output is correct
15 Correct 194 ms 6460 KB Output is correct
16 Correct 197 ms 6696 KB Output is correct
17 Correct 177 ms 6416 KB Output is correct
18 Correct 1780 ms 62760 KB Output is correct
19 Correct 1890 ms 62864 KB Output is correct
20 Correct 1967 ms 62968 KB Output is correct
21 Correct 164 ms 6468 KB Output is correct
22 Correct 174 ms 6492 KB Output is correct
23 Correct 404 ms 324 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 184 ms 6384 KB Output is correct
3 Correct 194 ms 6464 KB Output is correct
4 Correct 1991 ms 62788 KB Output is correct
5 Correct 189 ms 6852 KB Output is correct
6 Correct 204 ms 6840 KB Output is correct
7 Correct 207 ms 6900 KB Output is correct
8 Correct 205 ms 6860 KB Output is correct
9 Correct 200 ms 6816 KB Output is correct
10 Correct 181 ms 6872 KB Output is correct
11 Correct 192 ms 6804 KB Output is correct
12 Correct 194 ms 7012 KB Output is correct
13 Correct 197 ms 6916 KB Output is correct
14 Correct 2196 ms 63476 KB Output is correct
15 Correct 167 ms 6212 KB Output is correct
16 Correct 1866 ms 63196 KB Output is correct
17 Correct 1812 ms 63080 KB Output is correct
18 Correct 0 ms 204 KB Output is correct

Subtask #8
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 17 ms 844 KB Output is correct
3 Correct 16 ms 820 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 16 ms 844 KB Output is correct
17 Correct 178 ms 6420 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 2 ms 204 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 857 ms 272 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 1795 ms 62876 KB Output is correct
31 Correct 1875 ms 62864 KB Output is correct
32 Correct 2001 ms 62900 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 1800 ms 63044 KB Output is correct
35 Correct 1892 ms 62800 KB Output is correct
36 Correct 1821 ms 62852 KB Output is correct
37 Correct 2017 ms 62888 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 156 ms 6376 KB Output is correct
40 Correct 158 ms 6380 KB Output is correct
41 Correct 160 ms 6420 KB Output is correct
42 Correct 181 ms 6716 KB Output is correct
43 Correct 163 ms 6448 KB Output is correct
44 Correct 162 ms 6516 KB Output is correct
45 Correct 176 ms 6484 KB Output is correct
46 Correct 208 ms 6516 KB Output is correct
47 Correct 167 ms 6468 KB Output is correct
48 Correct 194 ms 6460 KB Output is correct
49 Correct 197 ms 6696 KB Output is correct
50 Correct 177 ms 6416 KB Output is correct
51 Correct 1780 ms 62760 KB Output is correct
52 Correct 1890 ms 62864 KB Output is correct
53 Correct 1967 ms 62968 KB Output is correct
54 Correct 164 ms 6468 KB Output is correct
55 Correct 174 ms 6492 KB Output is correct
56 Correct 404 ms 324 KB Output is correct
57 Correct 0 ms 204 KB Output is correct
58 Correct 184 ms 6384 KB Output is correct
59 Correct 194 ms 6464 KB Output is correct
60 Correct 1991 ms 62788 KB Output is correct
61 Correct 189 ms 6852 KB Output is correct
62 Correct 204 ms 6840 KB Output is correct
63 Correct 207 ms 6900 KB Output is correct
64 Correct 205 ms 6860 KB Output is correct
65 Correct 200 ms 6816 KB Output is correct
66 Correct 181 ms 6872 KB Output is correct
67 Correct 192 ms 6804 KB Output is correct
68 Correct 194 ms 7012 KB Output is correct
69 Correct 197 ms 6916 KB Output is correct
70 Correct 2196 ms 63476 KB Output is correct
71 Correct 167 ms 6212 KB Output is correct
72 Correct 1866 ms 63196 KB Output is correct
73 Correct 1812 ms 63080 KB Output is correct
74 Correct 0 ms 204 KB Output is correct
75 Correct 1 ms 204 KB Output is correct
76 Correct 0 ms 204 KB Output is correct
77 Correct 1 ms 204 KB Output is correct
78 Correct 1 ms 204 KB Output is correct
79 Correct 17 ms 904 KB Output is correct
80 Correct 2021 ms 63084 KB Output is correct
81 Correct 1929 ms 63064 KB Output is correct
82 Correct 2117 ms 63164 KB Output is correct
83 Correct 2103 ms 63108 KB Output is correct
84 Correct 2172 ms 63264 KB Output is correct
85 Correct 2088 ms 63540 KB Output is correct
86 Correct 506 ms 908 KB Output is correct
87 Correct 1 ms 204 KB Output is correct