Submission #240438

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
240438	2020-06-19T16:20:13 Z	valerikk	Strange Device (APIO19_strange_device)	C++14	20 / 100	2648 ms	250896 KB

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> good;

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(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_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) {
                    good.eb(L, R);
                } else {
                    good.eb(0, R);
                    good.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(good));
    for (int i = 1; i < len(good); i++) {
        if (good[i].x <= min(good[i - 1].y, good[i].y)) {
            good[i].x = good[i - 1].x;
            good[i].y = max(good[i].y, good[i - 1].y);
        }
    }
    vector<pii> tmp;
    for (int i = 0; i < len(good); i++) {
        if (i == 0 || good[i].x > tmp.back().y) tmp.pb(good[i]);
    }
    good = tmp;
    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(events); i++) {
        if (!check(events[i].p)) {
            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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	17 ms	1276 KB	Output is correct
3	Correct	15 ms	1276 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	308 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Incorrect	5 ms	384 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Incorrect	4 ms	384 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Incorrect	7 ms	512 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	1171 ms	109920 KB	Output is correct
3	Incorrect	2582 ms	250896 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	1171 ms	109920 KB	Output is correct
3	Incorrect	2582 ms	250896 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	1171 ms	109920 KB	Output is correct
3	Incorrect	2582 ms	250896 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	79 ms	6660 KB	Output is correct
3	Correct	111 ms	6632 KB	Output is correct
4	Correct	2376 ms	98984 KB	Output is correct
5	Correct	114 ms	6628 KB	Output is correct
6	Correct	117 ms	6632 KB	Output is correct
7	Correct	113 ms	6628 KB	Output is correct
8	Correct	134 ms	7384 KB	Output is correct
9	Correct	133 ms	7388 KB	Output is correct
10	Correct	88 ms	6632 KB	Output is correct
11	Correct	72 ms	6608 KB	Output is correct
12	Correct	75 ms	6628 KB	Output is correct
13	Correct	119 ms	6640 KB	Output is correct
14	Correct	970 ms	49712 KB	Output is correct
15	Correct	86 ms	6628 KB	Output is correct
16	Correct	787 ms	49792 KB	Output is correct
17	Correct	2648 ms	98916 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	17 ms	1276 KB	Output is correct
3	Correct	15 ms	1276 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	308 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Incorrect	5 ms	384 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Submission #240438

Compilation message