oj.uz

Submission #240435

# Submission time Handle Problem Language Result Execution time Memory
240435 2020-06-19T16:17:21 Z valerikk Strange Device (APIO19_strange_device) C++14
20 / 100
 2677 ms 250900 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 12 ms 1276 KB Output is correct
3 Correct 12 ms 1276 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 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 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 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 6 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 1183 ms 109996 KB Output is correct
3 Incorrect 2677 ms 250900 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 1183 ms 109996 KB Output is correct
3 Incorrect 2677 ms 250900 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 1183 ms 109996 KB Output is correct
3 Incorrect 2677 ms 250900 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 81 ms 6604 KB Output is correct
3 Correct 112 ms 6804 KB Output is correct
4 Correct 2498 ms 112160 KB Output is correct
5 Correct 126 ms 9664 KB Output is correct
6 Correct 121 ms 9560 KB Output is correct
7 Correct 119 ms 9704 KB Output is correct
8 Correct 148 ms 11096 KB Output is correct
9 Correct 154 ms 11096 KB Output is correct
10 Correct 93 ms 9296 KB Output is correct
11 Correct 76 ms 9328 KB Output is correct
12 Correct 82 ms 9316 KB Output is correct
13 Correct 129 ms 9944 KB Output is correct
14 Correct 1008 ms 63020 KB Output is correct
15 Correct 96 ms 9316 KB Output is correct
16 Correct 825 ms 56620 KB Output is correct
17 Correct 2654 ms 105748 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 12 ms 1276 KB Output is correct
3 Correct 12 ms 1276 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -