제출 #987755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987755		876pol	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	687 ms	100560 KiB

strange_device

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using int128 = __int128_t;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << "[";
    for (auto it = obj.begin(); it != obj.end(); it++) {
        out << &", "[2 * (it == obj.begin())] << *it;
    }
    return out << "]";
}

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, a, b;
    cin >> n >> a >> b;
    ll sz = min((int128)a * b / gcd(a, b + 1), (int128)1e18 + 5);
    set<pll> ss;
    auto insert = [&](pll p) {
        auto it = ss.lower_bound(p);
        while (it != ss.end() && it->first <= p.second) {
            p.second = max(p.second, it->second);
            it = ss.erase(it);
        }
        if (it != ss.begin() && p.first <= prev(it)->second) {
            p.first = min(p.first, prev(it)->first);
            p.second = max(p.second, prev(it)->second);
            ss.erase(prev(it));
        }
        ss.insert(p);
    };
    FOR(i, 0, n) {
        ll l, r;
        cin >> l >> r;
        if (r - l + 1 >= sz) {
            insert({0, sz - 1});
        } else {
            l %= sz;
            r %= sz;
            if (l <= r) {
                insert({l, r});
            } else {
                insert({0, r});
                insert({l, sz - 1});
            }
        }
    }
    ll ans = 0;
    TRAV(e, ss) ans += e.second - e.first + 1;
    cout << ans << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30