Submission #544210

#	Time	Username	Problem	Language	Result	Execution time	Memory
544210		Victor	Strange Device (APIO19_strange_device)	C++17	100 / 100	664 ms	37452 KiB

strange_device

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

struct Node {
    ll sum = 0, lo, hi, mset = INF;
    Node *l = 0, *r = 0;

    Node(ll L, ll R) : lo(L), hi(R) {}

    void set(ll L, ll R, ll x) {
        if (hi <= L || R <= lo) return;

        if (L <= lo && hi <= R) {
            mset = x;
            sum = (hi - lo) * mset;

        } else {
            push();
            l->set(L, R, x), r->set(L, R, x);
            sum = l->sum + r->sum;
        }
    }

    void push() {
        if (!l) {
            ll mid = (lo + hi) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);
        }

        if (mset != INF) {
            l->set(lo, hi, mset), r->set(lo, hi, mset);
            mset = INF;
        }
    }
};

int n;
ll A, B, len;
set<pll> segments;

void add(ll start, ll take) {
    ll stop = start + take;
    auto it = segments.lower_bound(pll(start, 0LL));
    vpll rem;

    while (it != segments.end()) {
        if (stop < it->first) break;

        stop = max(stop, it->second);
        rem.emplace_back(*it);
        ++it;
    }

    it = segments.lower_bound(pll(start, 0LL));
    while (it != segments.begin()) {
        --it;
        if (it->second < start) break;

        rem.emplace_back(*it);
        start = min(start, it->first);
        stop = max(stop, it->second);
    }

    trav(item,rem)segments.erase(item);
    segments.emplace(start,stop);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> A >> B;
    ll x = A / __gcd(A, B + 1);
    if (log10(x) + log10(B) > 18)
        len = ll(1e18);
    else
        len = B * x;

    // debug(len);
    while (n--) {
        ll lo, hi;
        cin >> lo >> hi;
        ++hi;

        if (hi - lo >= len)
            add(0,len);
        else {
            ll start = lo % len, take = min(hi - lo, (len - start));
            add(start, take);
            // cout<<"start = "<<start<<" stop = "<<start+take<<endl;

            if (start) {
                start = 0;
                take = (hi - lo) - take;
                add(start, take);
                // cout<<"start = "<<start<<" stop = "<<start+take<<endl;
            }
        }
        // cout<<endl;
    }

    ll ans=0;
    trav(segment,segments) ans+=segment.second-segment.first;
    cout<<ans<<endl;
    return 0;
}

• 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