Submission #240440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
240440	2020-06-19T16:23:51 Z	valerikk	Strange Device (APIO19_strange_device)	C++14	30 / 100	5000 ms	524292 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> 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));
    set<int> anime;
    for (auto el : good) {
        for (int i = el.x; i <= el.y; i++) anime.insert(i);
    }
    map<int, int> cnt;
    int have = 0, ans = len(anime) * b;
    for (int i = 0; i + 1 < len(evs); i++) {
        if (!anime.count(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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	12 ms	1148 KB	Output is correct
3	Correct	12 ms	1276 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	13 ms	1276 KB	Output is correct
17	Correct	77 ms	6632 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 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	4 ms	384 KB	Output is correct
2	Correct	7 ms	768 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	7 ms	640 KB	Output is correct
5	Execution timed out	5070 ms	126348 KB	Time limit exceeded

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	1076 ms	110260 KB	Output is correct
3	Runtime error	2536 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
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	1076 ms	110260 KB	Output is correct
3	Runtime error	2536 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
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	1076 ms	110260 KB	Output is correct
3	Runtime error	2536 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
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	84 ms	6756 KB	Output is correct
3	Correct	102 ms	6760 KB	Output is correct
4	Correct	2331 ms	99180 KB	Output is correct
5	Correct	115 ms	6760 KB	Output is correct
6	Correct	116 ms	6760 KB	Output is correct
7	Correct	115 ms	6756 KB	Output is correct
8	Correct	133 ms	7384 KB	Output is correct
9	Correct	133 ms	7512 KB	Output is correct
10	Correct	87 ms	6768 KB	Output is correct
11	Correct	69 ms	6764 KB	Output is correct
12	Correct	73 ms	6756 KB	Output is correct
13	Correct	121 ms	6760 KB	Output is correct
14	Correct	970 ms	49964 KB	Output is correct
15	Correct	84 ms	6760 KB	Output is correct
16	Correct	805 ms	49836 KB	Output is correct
17	Correct	2396 ms	99060 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	4 ms	384 KB	Output is correct
2	Correct	12 ms	1148 KB	Output is correct
3	Correct	12 ms	1276 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	13 ms	1276 KB	Output is correct
17	Correct	77 ms	6632 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct
22	Incorrect	4 ms	384 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Submission #240440

Compilation message