Submission #240444

#	Time	Username	Problem	Language	Result	Execution time	Memory
240444		valerikk	Strange Device (APIO19_strange_device)	C++14	45 / 100	5064 ms	251168 KiB

strange_device

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

#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(pii a, pii b) {
    return max(a.x, b.x) <= min(a.y, b.y);
}

pii unite(pii a, pii b) {
    assert(inter(a, b));
    return {min(a.x, b.x), max(a.y, b.y)};
}

struct Event {
    int x, type, p;

    Event() {}
    Event(int x, int type, int 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<pii> good;

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

bool check(int 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() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    int period = a / __gcd(a, b + 1);
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        int 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) {
                int L = (block_l + 1) % period, R = (block_r - 1) % period;
                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<pii> 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, 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);
    }
    cout << ans;
    return 0;
}

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