oj.uz

Submission #527653

# Submission time Handle Problem Language Result Execution time Memory
527653 2022-02-17T22:29:44 Z Olympia Strange Device (APIO19_strange_device) C++17
15 / 100
 2041 ms 63008 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;
    }
    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) {
        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);
    }
};
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 19 ms 900 KB Output isn't correct
3 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
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1920 ms 62836 KB Output is correct
3 Correct 1895 ms 62932 KB Output is correct
4 Correct 1997 ms 62868 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1920 ms 62836 KB Output is correct
3 Correct 1895 ms 62932 KB Output is correct
4 Correct 1997 ms 62868 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1878 ms 62900 KB Output is correct
7 Correct 1895 ms 62956 KB Output is correct
8 Correct 1884 ms 63008 KB Output is correct
9 Correct 2041 ms 62928 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1920 ms 62836 KB Output is correct
3 Correct 1895 ms 62932 KB Output is correct
4 Correct 1997 ms 62868 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 165 ms 6404 KB Output is correct
7 Correct 163 ms 6456 KB Output is correct
8 Correct 176 ms 6548 KB Output is correct
9 Correct 176 ms 6536 KB Output is correct
10 Correct 173 ms 6472 KB Output is correct
11 Correct 167 ms 6452 KB Output is correct
12 Correct 183 ms 6508 KB Output is correct
13 Correct 180 ms 6468 KB Output is correct
14 Correct 176 ms 6516 KB Output is correct
15 Correct 196 ms 6696 KB Output is correct
16 Incorrect 189 ms 6464 KB Output isn't correct
17 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 189 ms 6540 KB Output is correct
3 Correct 188 ms 6448 KB Output is correct
4 Correct 1902 ms 62936 KB Output is correct
5 Correct 189 ms 6468 KB Output is correct
6 Correct 191 ms 6416 KB Output is correct
7 Correct 191 ms 6500 KB Output is correct
8 Correct 192 ms 6548 KB Output is correct
9 Correct 181 ms 6468 KB Output is correct
10 Correct 166 ms 6424 KB Output is correct
11 Correct 181 ms 6532 KB Output is correct
12 Correct 175 ms 6468 KB Output is correct
13 Correct 186 ms 6524 KB Output is correct
14 Correct 1990 ms 62964 KB Output is correct
15 Incorrect 170 ms 6620 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 Incorrect 19 ms 900 KB Output isn't correct
3 Halted 0 ms 0 KB -