oj.uz

답안 #527631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527631 2022-02-17T20:59:10 Z Olympia 이상한 기계 (APIO19_strange_device) C++17
10 / 100
 1719 ms 47216 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<int,int>> intervals;
    void print () {
        for (auto& p: intervals) {
            cout << p.first << " " << p.second << '\n';
        }
        cout << '\n';
    }
    pair<int,int> leftIntersect (pair<int,int> p) {
        auto it = intervals.upper_bound({p.first + 1, -1});
        if (it == intervals.begin()) {
            return {-1, -1};
        }
        it--;
        pair<int,int> q = *it;
        if (q.second < p.first) {
            return {-1, -1};
        }
        return q;
    }
    pair<int,int> rightIntersect (pair<int,int> p) {
        auto it = intervals.upper_bound({p.second + 1, -1});
        if (it == intervals.begin()) {
            return {-1, -1};
        }
        it--;
        pair<int,int> q = *it;
        if (q.first > p.second) {
            return {-1, -1};
        }
        if (q.first < p.first) {
            return {-1, -1};
        }
        return q;
    }
    bool willChange (pair<int,int> p) {
        pair<int,int> 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<int,int> update_left (pair<int,int> p) {
//        cout << "UPDATE LEFT " << p.first << " " << p.second << '\n';
        pair<int,int> q = leftIntersect(p);
        if (q.first == -1 && q.second == -1) {
            return p;
        }
        if (q.second < p.first) {
            return p;
        }
//        cout << "ERASE\n";
        if (intervals.count(q)) intervals.erase(q);
        return {q.first, p.second};
    }
    pair<int,int> update_right (pair<int,int> p) {
//        cout << "UPDATE RIGHT " << p.first << " " << p.second << '\n';
        pair<int,int> q = rightIntersect(p);
        if (q.first == -1 && q.second == -1) {
            return p;
        }
        if (q.first > p.second) {
            return p;
        }
//        cout << "ERASE " << q.first << " " << q.second << '\n';
//        cout << "ADD " << p.first << " " << q.second << '\n';
        if (intervals.count(q)) intervals.erase(q);
        return {p.first, q.second};
    }
    void erase_in_between (pair<int,int> p) {
        auto it = intervals.lower_bound({p.first, -1});
        set<pair<int,int>> 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<int,int> p) {
//        cout << "ADD " << p.first << " " << p.second << '\n';
        if (!willChange(p)) { //if adding this interval will not change anything, then there is no point in adding this interval (i.e. if there is another interval which covers the given interval)
            return;
        }
        erase_in_between(p);
        pair<int,int> new_p = update_left(p);
        pair<int,int> new_p1 = update_right(new_p);
        intervals.insert(new_p1);
    }
};
int main () {
    int N;
    int64_t A, B;
    cin >> N >> A >> B;
    int64_t prod;
    if (A < LLONG_MAX/B) {
        prod = A * B;
    } else {
        prod = LLONG_MAX;
    }
    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, A * B - 1});
            continue;
        }
        x %= (A * B), y %= (prod);
        if (x <= y) {
            //cout << "T1\n";
            myInterval.add_interval({x, y});
        } else {
            //cout << "T2\n";
            swap(x, y);
            myInterval.add_interval({0, x});
            myInterval.add_interval({y, A * B - 1});
        }
    }
//    myInterval.print();
    int 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 15 ms 716 KB Output is correct
3 Correct 15 ms 648 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 3 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 889 ms 268 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1719 ms 47216 KB Output is correct
3 Incorrect 1427 ms 5956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1719 ms 47216 KB Output is correct
3 Incorrect 1427 ms 5956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1719 ms 47216 KB Output is correct
3 Incorrect 1427 ms 5956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 187 ms 4816 KB Output is correct
3 Incorrect 204 ms 4172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 15 ms 716 KB Output is correct
3 Correct 15 ms 648 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -