oj.uz

Submission #240448

# Submission time Handle Problem Language Result Execution time Memory
240448 2020-06-19T16:34:46 Z valerikk Strange Device (APIO19_strange_device) C++14
45 / 100
 5000 ms 219812 KB 
#include<bits/stdc++.h>
using namespace std;

template<class T = int>
inline T fast_scan() {
    T res = 0;
    char tmp;
    do {
        tmp = getchar();
    } while (tmp < '0' || tmp > '9');
    while (tmp >= '0' && tmp <= '9') {
        res = res * 10 + tmp - '0';
        tmp = getchar();
    }
    return res;
}

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

pll unite(pll a, pll b) {
    return {min(a.x, b.x), max(a.y, b.y)};
}

struct Event {
    ll x;
    int type;
    ll p;

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

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

bool check(ll 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() {
    int n = fast_scan();
    ll a = fast_scan<ll>(), b = fast_scan<ll>();
    ll period = a / __gcd(a, b + 1);
    for (int i = 0; i < n; ++i) {
        ll l = fast_scan<ll>(), r = fast_scan<ll>();
        ll 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) {
                ll 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<pll> 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;
    ll 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);
    }
    printf("%lld", ans);
    return 0;
}

Subtask #1
10.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 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 14 ms 1276 KB Output is correct
17 Correct 78 ms 6628 KB Output is correct
18 Correct 4 ms 256 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 700 ms 126420 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 1105 ms 94356 KB Output is correct
3 Correct 2919 ms 219812 KB Output is correct
4 Correct 4316 ms 219652 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 1105 ms 94356 KB Output is correct
3 Correct 2919 ms 219812 KB Output is correct
4 Correct 4316 ms 219652 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 3820 ms 172644 KB Output is correct
7 Correct 1036 ms 63236 KB Output is correct
8 Correct 3032 ms 172776 KB Output is correct
9 Correct 4943 ms 172628 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 1105 ms 94356 KB Output is correct
3 Correct 2919 ms 219812 KB Output is correct
4 Correct 4316 ms 219652 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 167 ms 14444 KB Output is correct
7 Correct 281 ms 17544 KB Output is correct
8 Correct 284 ms 17616 KB Output is correct
9 Correct 310 ms 17684 KB Output is correct
10 Correct 183 ms 12772 KB Output is correct
11 Correct 274 ms 17540 KB Output is correct
12 Correct 285 ms 17676 KB Output is correct
13 Correct 280 ms 17672 KB Output is correct
14 Correct 73 ms 6628 KB Output is correct
15 Correct 273 ms 14652 KB Output is correct
16 Correct 102 ms 6668 KB Output is correct
17 Correct 290 ms 17544 KB Output is correct
18 Execution timed out 5067 ms 172624 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 78 ms 6628 KB Output is correct
3 Correct 103 ms 6628 KB Output is correct
4 Correct 2223 ms 99192 KB Output is correct
5 Correct 116 ms 6640 KB Output is correct
6 Correct 114 ms 6628 KB Output is correct
7 Correct 110 ms 6564 KB Output is correct
8 Correct 132 ms 7052 KB Output is correct
9 Correct 131 ms 7128 KB Output is correct
10 Correct 92 ms 6632 KB Output is correct
11 Correct 71 ms 6632 KB Output is correct
12 Correct 75 ms 6640 KB Output is correct
13 Correct 120 ms 6628 KB Output is correct
14 Correct 970 ms 49848 KB Output is correct
15 Correct 85 ms 6632 KB Output is correct
16 Correct 786 ms 49852 KB Output is correct
17 Correct 2569 ms 99204 KB Output is correct
18 Correct 5 ms 256 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 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 4 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 14 ms 1276 KB Output is correct
17 Correct 78 ms 6628 KB Output is correct
18 Correct 4 ms 256 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 4 ms 256 KB Output is correct
22 Incorrect 5 ms 256 KB Output isn't correct
23 Halted 0 ms 0 KB -