제출 #240502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240502		valerikk	이상한 기계 (APIO19_strange_device)	C++14	45 / 100	5081 ms	221636 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
*/

template<class T = int>
inline T fast_scan() {
    T res = 0;
    char tmp;
    do tmp = getchar(); while (tmp < '0' || tmp > '9');
    while (tmp >= '0' && tmp <= '9') {
        res = res * 10 + tmp - '0';
        tmp = getchar();
    }
    return res;
}

//#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple

#define len(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

bool inter(pll a, pll b) {
    return max(a.x, b.x) <= min(a.y, b.y);
}

pll unite(pll a, pll b) {
    return {min(a.x, b.x), max(a.y, b.y)};
}

struct Event {
    ll x;
    int type;
    ll p;

    Event() {}
    Event(ll x, int type, ll p) : x(x), type(type), p(p) {}
};

bool operator<(const Event& a, const Event& b) {
    return mt(a.x, a.type) < mt(b.x, b.type);
}

vector<Event> evs;
vector<pll> good;

void add_ev(ll l, ll r, ll p) {
    evs.eb(l, 0, p);
    evs.eb(r + 1, 1, p);
}

bool check(ll x) {
    int l = -1, r = len(good);
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (good[mid].y >= x) r = mid; else l = mid;
    }
    if (r == len(good)) return 0;
    return good[r].x <= x;
}

int32_t main() {
    int n = fast_scan();
    ll a = fast_scan<ll>(), b = fast_scan<ll>();
    ll period = a / __gcd(a, b + 1);
    for (int i = 0; i < n; ++i) {
        ll l = fast_scan<ll>(), r = fast_scan<ll>();
        ll block_l = l / b, block_r = r / b;
        if (block_l == block_r) {
            add_ev(l % b, r % b, block_l % period);
        } else {
            if (block_r - block_l > 1) {
                ll L = (block_l + 1) % period, R = (block_r - 1) % period;
                if (block_r - block_l - 1 >= period) {
                    L = 0;
                    R = period - 1;
                }
                if (L <= R) {
                    good.eb(L, R);
                } else {
                    good.eb(0, R);
                    good.eb(L, period - 1);
                }
            }
            add_ev(l % b, b - 1, block_l % period);
            add_ev(0, r % b, block_r % period);
        }
    }
    sort(all(evs));
    sort(all(good));
    vector<pll> st;
    for (auto val : good) {
        if (!st.empty() && inter(val, st.back())) st.back() = unite(st.back(), val); else st.pb(val);
    }
    good = st;
    map<int, int> cnt;
    int have = 0;
    ll ans = 0;
    for (auto val : good) ans += (val.y - val.x + 1) * b;
    for (int i = 0; i + 1 < len(evs); ++i) {
        if (!check(evs[i].p)) {
            if (evs[i].type == 0) {
                ++cnt[evs[i].p];
                if (cnt[evs[i].p] == 1) ++have;
            } else {
                --cnt[evs[i].p];
                if (cnt[evs[i].p] == 0) --have;
            }
        }
        ans += have * (evs[i + 1].x - evs[i].x);
    }
    printf("%lld", ans);
    return 0;
}

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