oj.uz

Submission #47700

# Submission time Handle Problem Language Result Execution time Memory
47700 2018-05-06T10:31:29 Z qoo2p5 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 245 ms 118616 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = 1 << 18;

int n, k;
int a[N], b[N];
pair<int, int> op[N];

int sum[2 * N], mi[2 * N];

void upd(int i, int v) {
    i += N;
    sum[i] = 1;
    mi[i] = v;
    i /= 2;
    while (i) {
        sum[i] = sum[2 * i] + sum[2 * i + 1];
        mi[i] = min(mi[2 * i], mi[2 * i + 1]);
        i /= 2;
    }
}

int get(int i, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) {
        return 0;
    }
    if (l <= tl && tr <= r) {
        return sum[i];
    }
    int tm = (tl + tr) / 2;
    return get(2 * i, tl, tm, l, r) + get(2 * i + 1, tm, tr, l, r);
}

int find(int i, int tl, int tr, int l, int r, int v) {
    if (tl >= r || tr <= l || mi[i] >= v) {
        return -1;
    }
    if (tl == tr - 1) {
        return tl;
    }
    int tm = (tl + tr) / 2;
    int res = find(2 * i + 1, tm, tr, l, r, v);
    if (res != -1) {
        return res;
    }
    return find(2 * i, tl, tm, l, r, v);
}

void run() {
    cin >> n >> k;
    rep(i, 0, n) {
        cin >> a[i] >> b[i];
    }
    rep(i, 0, k) {
        cin >> op[i].first;
        op[i].second = i;
    }
    sort(op, op + k);
    
    vector<int> p(n);
    rep(i, 0, n) {
        p[i] = i;
    }
    sort(all(p), [] (int i, int j) {
        return min(a[i], b[i]) > min(a[j], b[j]);
    });
    
    int ptr = k - 1;
    rep(i, 0, 2 * N) {
        mi[i] = INF;
    }
    ll ans = 0;
    rep(ii, 0, n) {
        int i = p[ii];
        while (ptr >= 0 && op[ptr].first >= min(a[i], b[i])) {
            upd(op[ptr].second, op[ptr].first);
            ptr--;
        }
        
        int pos = find(1, 0, N, 0, N, max(a[i], b[i]));
        if (pos != -1 && a[i] < b[i]) {
            swap(a[i], b[i]);
        }
        int cnt = get(1, 0, N, pos + 1, N);
        ans += (cnt % 2 ? b[i] : a[i]);
    }
    
    cout << ans << "\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2536 KB Output is correct
3 Correct 4 ms 2720 KB Output is correct
4 Correct 4 ms 2772 KB Output is correct
5 Correct 5 ms 2772 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 4 ms 2772 KB Output is correct
10 Correct 4 ms 2772 KB Output is correct
11 Correct 4 ms 2772 KB Output is correct
12 Correct 4 ms 2772 KB Output is correct
13 Correct 4 ms 2772 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2924 KB Output is correct
2 Correct 22 ms 3860 KB Output is correct
3 Correct 31 ms 5032 KB Output is correct
4 Correct 42 ms 6440 KB Output is correct
5 Correct 42 ms 7632 KB Output is correct
6 Correct 42 ms 8792 KB Output is correct
7 Correct 42 ms 9964 KB Output is correct
8 Correct 41 ms 11120 KB Output is correct
9 Correct 32 ms 11744 KB Output is correct
10 Correct 32 ms 12448 KB Output is correct
11 Correct 33 ms 13168 KB Output is correct
12 Correct 32 ms 14020 KB Output is correct
13 Correct 34 ms 14872 KB Output is correct
14 Correct 39 ms 16108 KB Output is correct
15 Correct 37 ms 17272 KB Output is correct
16 Correct 38 ms 18376 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 20548 KB Output is correct
2 Correct 102 ms 23956 KB Output is correct
3 Correct 135 ms 28408 KB Output is correct
4 Correct 212 ms 35488 KB Output is correct
5 Correct 70 ms 35488 KB Output is correct
6 Correct 222 ms 43288 KB Output is correct
7 Correct 217 ms 49040 KB Output is correct
8 Correct 225 ms 54780 KB Output is correct
9 Correct 237 ms 60596 KB Output is correct
10 Correct 233 ms 66420 KB Output is correct
11 Correct 205 ms 72088 KB Output is correct
12 Correct 245 ms 77944 KB Output is correct
13 Correct 224 ms 83872 KB Output is correct
14 Correct 166 ms 88880 KB Output is correct
15 Correct 160 ms 94036 KB Output is correct
16 Correct 165 ms 99176 KB Output is correct
17 Correct 158 ms 103124 KB Output is correct
18 Correct 188 ms 106904 KB Output is correct
19 Correct 183 ms 112692 KB Output is correct
20 Correct 181 ms 118616 KB Output is correct