oj.uz

Submission #527633

# Submission time Handle Problem Language Result Execution time Memory
527633 2022-02-17T21:01:29 Z Olympia Strange Device (APIO19_strange_device) C++17
10 / 100
 2243 ms 67516 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) {
//        cout << "UPDATE LEFT " << p.first << " " << p.second << '\n';
        pair<int64_t,int64_t> 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<int64_t,int64_t> update_right (pair<int64_t,int64_t> p) {
//        cout << "UPDATE RIGHT " << p.first << " " << p.second << '\n';
        pair<int64_t,int64_t> 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<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) {
//        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<int64_t,int64_t> new_p = update_left(p);
        pair<int64_t,int64_t> 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();
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 17 ms 796 KB Output is correct
3 Correct 20 ms 908 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 920 ms 268 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1974 ms 62856 KB Output is correct
3 Incorrect 2055 ms 62932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1974 ms 62856 KB Output is correct
3 Incorrect 2055 ms 62932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1974 ms 62856 KB Output is correct
3 Incorrect 2055 ms 62932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 219 ms 6596 KB Output is correct
3 Correct 214 ms 6900 KB Output is correct
4 Correct 2227 ms 67284 KB Output is correct
5 Correct 207 ms 10300 KB Output is correct
6 Correct 213 ms 10120 KB Output is correct
7 Correct 205 ms 10160 KB Output is correct
8 Correct 214 ms 10280 KB Output is correct
9 Correct 203 ms 10132 KB Output is correct
10 Correct 174 ms 10120 KB Output is correct
11 Correct 199 ms 10168 KB Output is correct
12 Correct 193 ms 10232 KB Output is correct
13 Correct 234 ms 10196 KB Output is correct
14 Correct 2243 ms 67516 KB Output is correct
15 Incorrect 203 ms 10160 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 17 ms 796 KB Output is correct
3 Correct 20 ms 908 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -