oj.uz

Submission #527634

# Submission time Handle Problem Language Result Execution time Memory
527634 2022-02-17T21:02:47 Z Olympia Strange Device (APIO19_strange_device) C++17
10 / 100
 2134 ms 65000 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, prod - 1});
            continue;
        }
        x %= (prod), 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, prod - 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 1 ms 204 KB Output is correct
2 Correct 17 ms 1156 KB Output is correct
3 Correct 16 ms 1228 KB Output is correct
4 Incorrect 1 ms 292 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 1 ms 204 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 292 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 304 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 304 KB Output is correct
5 Correct 867 ms 2384 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1810 ms 64976 KB Output is correct
3 Incorrect 2035 ms 65000 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 296 KB Output is correct
2 Correct 1810 ms 64976 KB Output is correct
3 Incorrect 2035 ms 65000 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 296 KB Output is correct
2 Correct 1810 ms 64976 KB Output is correct
3 Incorrect 2035 ms 65000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 183 ms 8324 KB Output is correct
3 Correct 204 ms 8436 KB Output is correct
4 Correct 1952 ms 64432 KB Output is correct
5 Correct 189 ms 8100 KB Output is correct
6 Correct 201 ms 7964 KB Output is correct
7 Correct 192 ms 8004 KB Output is correct
8 Correct 185 ms 8060 KB Output is correct
9 Correct 187 ms 8048 KB Output is correct
10 Correct 166 ms 8040 KB Output is correct
11 Correct 175 ms 8004 KB Output is correct
12 Correct 170 ms 7840 KB Output is correct
13 Correct 194 ms 7980 KB Output is correct
14 Correct 2134 ms 64200 KB Output is correct
15 Incorrect 181 ms 7748 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 17 ms 1156 KB Output is correct
3 Correct 16 ms 1228 KB Output is correct
4 Incorrect 1 ms 292 KB Output isn't correct
5 Halted 0 ms 0 KB -