oj.uz

Submission #527649

# Submission time Handle Problem Language Result Execution time Memory
527649 2022-02-17T21:56:22 Z Olympia Strange Device (APIO19_strange_device) C++17
10 / 100
 2110 ms 67452 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 < 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) {
            //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 22 ms 1216 KB Output is correct
3 Correct 21 ms 1188 KB Output is correct
4 Incorrect 1 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 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 344 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 917 ms 2516 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1877 ms 67452 KB Output is correct
3 Incorrect 1999 ms 67344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1877 ms 67452 KB Output is correct
3 Incorrect 1999 ms 67344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1877 ms 67452 KB Output is correct
3 Incorrect 1999 ms 67344 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 200 ms 10152 KB Output is correct
3 Correct 202 ms 10152 KB Output is correct
4 Correct 1986 ms 67004 KB Output is correct
5 Correct 193 ms 10124 KB Output is correct
6 Correct 195 ms 10212 KB Output is correct
7 Correct 196 ms 10340 KB Output is correct
8 Correct 189 ms 10140 KB Output is correct
9 Correct 246 ms 10176 KB Output is correct
10 Correct 172 ms 10184 KB Output is correct
11 Correct 173 ms 10180 KB Output is correct
12 Correct 199 ms 10272 KB Output is correct
13 Correct 188 ms 10176 KB Output is correct
14 Correct 2110 ms 66768 KB Output is correct
15 Incorrect 192 ms 10208 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 22 ms 1216 KB Output is correct
3 Correct 21 ms 1188 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -