oj.uz

Submission #411419

# Submission time Handle Problem Language Result Execution time Memory
411419 2021-05-25T09:31:53 Z SolarSystem Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 506 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

using ll           = long long;
using ld           = long double;
using pii          = pair<int, int>;
using pll          = pair<long, long>;
using vi           = vector<int>;
using vl           = vector<long long>;

#define pb             push_back
#define F              first
#define S              second
#define sz(a)          int((a).size())
#define all(a)         (a).begin(), (a).end()
#define rall(a)        (a).rbegin(), (a).rend()
#define sum(a)         ( accumulate((a).begin(), (a).end(), 0LL))
#define lowb(a, x)     ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x)     ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define yes            cout << "YES" << endl
#define no             cout << "NO"  << endl

void fastIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); }

const ll mod = 1e9 + 7;

struct WaveletTree {
    vi b;
    int lo, hi;
    WaveletTree *l, *r;

    WaveletTree (int *i, int *j, int x, int y) {
        lo = x, hi = y;
        if (lo == hi || i >= j) return;

        int mid = (lo + hi) / 2;
        b.pb(0);
        for (auto it = i; it != j; it++) {
            b.pb(b.back() + (*it <= mid));
        }

        auto k = stable_partition(i, j, [mid] (int x) {return x <= mid;});
        l = new WaveletTree(i, k, lo, mid);
        r = new WaveletTree(k, j, mid + 1, hi);
    }

    int query(int l, int r, int k) {
        if (l > r || k < lo) return 0;
        if (hi <= k) return r - l + 1;

        int lb = b[l - 1], rb = b[r];
        return this->l->query(lb + 1, rb, k) + this->r->query(l - lb, r - rb, k);
    }

    int query(int l, int r, int x, int y) {
        l++; r++;

        if (y < x) return 0;
        return query(l, r, y) - query(l, r, x - 1);
    }
};

void solve() {
    int n, k;
    cin >> n >> k;

    vi a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    int t[k];
    for (int &u: t) cin >> u;

    WaveletTree T(t, t + k, 1, 1e9);

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int x = T.query(0, k - 1, min(a[i], b[i]), max(a[i], b[i]) - 1);

        if (x == 0) {
            if (T.query(0, k - 1, max(a[i], b[i]), 1e9) % 2) {
                ans += b[i];
            } else {
                ans += a[i];
            }
        } else {
            int l = -1, r = k - 1;

            while (l + 1 < r) {
                int m = (l + r) / 2;

                if (T.query(0, m, min(a[i], b[i]), max(a[i], b[i]) - 1) == x) {
                    r = m;
                } else {
                    l = m;
                }
            }

            if (T.query(r + 1, k - 1, max(a[i], b[i]), 1e9) % 2) {
                ans += min(a[i], b[i]);
            } else {
                ans += max(a[i], b[i]);
            }
        }
    }

    cout << ans;
}

int main() {
    fastIO();

    cout << setprecision(15) << fixed;

    int t = 1;
    // cin >> t;

    while (t--) solve();

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3408 KB Output is correct
2 Correct 7 ms 3524 KB Output is correct
3 Correct 9 ms 3532 KB Output is correct
4 Correct 11 ms 3532 KB Output is correct
5 Correct 9 ms 3532 KB Output is correct
6 Correct 9 ms 3532 KB Output is correct
7 Correct 9 ms 3532 KB Output is correct
8 Correct 9 ms 3548 KB Output is correct
9 Correct 8 ms 3404 KB Output is correct
10 Correct 9 ms 588 KB Output is correct
11 Correct 9 ms 3404 KB Output is correct
12 Correct 9 ms 3496 KB Output is correct
13 Correct 9 ms 3552 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3408 KB Output is correct
2 Correct 7 ms 3524 KB Output is correct
3 Correct 9 ms 3532 KB Output is correct
4 Correct 11 ms 3532 KB Output is correct
5 Correct 9 ms 3532 KB Output is correct
6 Correct 9 ms 3532 KB Output is correct
7 Correct 9 ms 3532 KB Output is correct
8 Correct 9 ms 3548 KB Output is correct
9 Correct 8 ms 3404 KB Output is correct
10 Correct 9 ms 588 KB Output is correct
11 Correct 9 ms 3404 KB Output is correct
12 Correct 9 ms 3496 KB Output is correct
13 Correct 9 ms 3552 KB Output is correct
14 Correct 99 ms 27584 KB Output is correct
15 Correct 262 ms 51780 KB Output is correct
16 Correct 333 ms 74572 KB Output is correct
17 Correct 499 ms 97332 KB Output is correct
18 Correct 490 ms 97356 KB Output is correct
19 Correct 473 ms 97356 KB Output is correct
20 Correct 486 ms 97320 KB Output is correct
21 Correct 459 ms 97240 KB Output is correct
22 Correct 506 ms 16076 KB Output is correct
23 Correct 505 ms 14788 KB Output is correct
24 Correct 481 ms 12788 KB Output is correct
25 Correct 496 ms 19220 KB Output is correct
26 Correct 376 ms 96112 KB Output is correct
27 Correct 428 ms 97164 KB Output is correct
28 Correct 429 ms 93404 KB Output is correct
29 Correct 302 ms 97272 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3408 KB Output is correct
2 Correct 7 ms 3524 KB Output is correct
3 Correct 9 ms 3532 KB Output is correct
4 Correct 11 ms 3532 KB Output is correct
5 Correct 9 ms 3532 KB Output is correct
6 Correct 9 ms 3532 KB Output is correct
7 Correct 9 ms 3532 KB Output is correct
8 Correct 9 ms 3548 KB Output is correct
9 Correct 8 ms 3404 KB Output is correct
10 Correct 9 ms 588 KB Output is correct
11 Correct 9 ms 3404 KB Output is correct
12 Correct 9 ms 3496 KB Output is correct
13 Correct 9 ms 3552 KB Output is correct
14 Correct 99 ms 27584 KB Output is correct
15 Correct 262 ms 51780 KB Output is correct
16 Correct 333 ms 74572 KB Output is correct
17 Correct 499 ms 97332 KB Output is correct
18 Correct 490 ms 97356 KB Output is correct
19 Correct 473 ms 97356 KB Output is correct
20 Correct 486 ms 97320 KB Output is correct
21 Correct 459 ms 97240 KB Output is correct
22 Correct 506 ms 16076 KB Output is correct
23 Correct 505 ms 14788 KB Output is correct
24 Correct 481 ms 12788 KB Output is correct
25 Correct 496 ms 19220 KB Output is correct
26 Correct 376 ms 96112 KB Output is correct
27 Correct 428 ms 97164 KB Output is correct
28 Correct 429 ms 93404 KB Output is correct
29 Correct 302 ms 97272 KB Output is correct
30 Runtime error 447 ms 262148 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -