Submission #240435

#	Time	Username	Problem	Language	Result	Execution time	Memory
240435		valerikk	Strange Device (APIO19_strange_device)	C++14	20 / 100	2677 ms	250900 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()

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> events;
vector<pii> always;

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

bool check(int x) {
    int l = -1, r = len(always);
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (always[mid].y >= x) r = mid; else l = mid;
    }
    if (r == len(always)) return 0;
    return always[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_event(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) {
                    always.eb(L, R);
                } else {
                    always.eb(0, R);
                    always.eb(L, period - 1);
                }
            }
            add_event(l % b, b - 1, block_l % period);
            add_event(0, r % b, block_r % period);
        }
    }
    sort(all(events));
    sort(all(always));
    for (int i = 1; i < len(always); i++) {
        if (always[i].x <= min(always[i - 1].y, always[i].y)) {
            always[i].x = always[i - 1].x;
            always[i].y = max(always[i].y, always[i - 1].y);
        }
    }
    vector<pii> tmp;
    for (int i = 0; i < len(always); i++) {
        if (i == 0 || always[i].x > always[i - 1].y) tmp.pb(always[i]);
    }
    always = tmp;
    map<int, int> cnt;
    int have = 0, ans = 0;
    for (auto val : always) ans += (val.y - val.x + 1) * b;
    for (int i = 0; i + 1 < len(events); i++) {
        if (check(events[i].p)) continue;
        if (events[i].type == 0) {
            cnt[events[i].p]++;
            if (cnt[events[i].p] == 1) have++;
        } else {
            cnt[events[i].p]--;
            if (cnt[events[i].p] == 0) have--;
        }
        ans += have * (events[i + 1].x - events[i].x);
    }
    cout << ans;
    return 0;
}

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