oj.uz

Submission #361425

# Submission time Handle Problem Language Result Execution time Memory
361425 2021-01-30T03:07:35 Z RyoPham Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 635 ms 41820 KB 
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 6e5 + 5;

int n, k;
pii cards[maxn];
int t[maxn];

vector<int> vals;

vector<int> pos_val[maxn];

struct segment_tree
{
    int max_pos[maxn * 4], total[maxn * 4];

    void add_pos(int x, int l, int r, int p, int k)
    {
        if(l == r)
        {
            max_pos[x] = max(max_pos[x], k);
            return;
        }
        int mid = (l + r) / 2;
        if(p <= mid) add_pos(x * 2, l, mid, p, k);
        else add_pos(x * 2 + 1, mid + 1, r, p, k);
        max_pos[x] = max(max_pos[x * 2], max_pos[x * 2 + 1]);
    }

    int get_max_pos(int x, int l, int r, int L, int R)
    {
        if(L > r || l > R) return 0;
        if(l >= L && r <= R)
            return max_pos[x];
        int mid = (l + r) / 2;
        return max(get_max_pos(x * 2, l, mid, L, R),
                   get_max_pos(x * 2 + 1, mid + 1, r, L, R));
    }

    void add(int x, int l, int r, int p)
    {
        if(l == r)
        {
            ++total[x];
            return;
        }
        int mid = (l + r) / 2;
        if(p <= mid) add(x * 2, l, mid, p);
        else add(x * 2 + 1, mid + 1, r, p);
        total[x] = total[x * 2] + total[x * 2 + 1];
    }

    int get_total(int x, int l, int r, int L, int R)
    {
        if(L > r || l > R || L > R) return 0;
        if(l >= L && r <= R)
            return total[x];
        int mid = (l + r) / 2;
        return get_total(x * 2, l, mid, L, R) + get_total(x * 2 + 1, mid + 1, r, L, R);
    }
} tree;

void read_input()
{
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> cards[i].fi >> cards[i].se;
    for(int i = 1; i <= k; ++i)
        cin >> t[i];
}

int lwb(const vector<int>&arr, int k)
{
    return lower_bound(arr.begin(), arr.end(), k) - arr.begin() + 1;
}

void init()
{
    for(int i = 1; i <= n; ++i)
    {
        vals.push_back(cards[i].fi);
        vals.push_back(cards[i].se);
    }
    for(int i = 1; i <= k; ++i)
        vals.push_back(t[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    for(int i = 1; i <= n; ++i)
    {
        cards[i].fi = lwb(vals, cards[i].fi);
        cards[i].se = lwb(vals, cards[i].se);
    }
    for(int i = 1; i <= k; ++i)
    {
        t[i] = lwb(vals, t[i]);
        tree.add_pos(1, 1, sz(vals), t[i], i);
        pos_val[t[i]].push_back(i);
    }
    sort(cards + 1, cards + n + 1, [](pii p, pii q)
         {
             return max(p.fi, p.se) > max(q.fi, q.se);
         });
}

void solve()
{
    lli ans = 0;
    for(int i = 1, j = sz(vals); i <= n; ++i)
    {
        if(cards[i].fi == cards[i].se)
        {
            ans += vals[cards[i].fi - 1];
            continue;
        }
        int mx = max(cards[i].fi, cards[i].se);
        int mn = min(cards[i].fi, cards[i].se);
        while(j >= mx)
        {
            for(auto&p: pos_val[j])
                tree.add(1, 1, k, p);
            --j;
        }
        int p = tree.get_max_pos(1, 1, sz(vals), mn, mx - 1);
        int t = tree.get_total(1, 1, k, p + 1, k);
        if(p > 0)
            ans += (t & 1 ? vals[mn - 1] : vals[mx - 1]);
        else ans += (t & 1 ? vals[cards[i].se - 1] : vals[cards[i].fi - 1]);
    }
    cout << ans << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14572 KB Output is correct
2 Correct 11 ms 14572 KB Output is correct
3 Correct 12 ms 14572 KB Output is correct
4 Correct 12 ms 14700 KB Output is correct
5 Correct 12 ms 14572 KB Output is correct
6 Correct 12 ms 14572 KB Output is correct
7 Correct 12 ms 14572 KB Output is correct
8 Correct 12 ms 14572 KB Output is correct
9 Correct 11 ms 14572 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 13 ms 14572 KB Output is correct
12 Correct 11 ms 14572 KB Output is correct
13 Correct 12 ms 14572 KB Output is correct
14 Correct 29 ms 15708 KB Output is correct
15 Correct 48 ms 16880 KB Output is correct
16 Correct 71 ms 18284 KB Output is correct
17 Correct 117 ms 19308 KB Output is correct
18 Correct 101 ms 19308 KB Output is correct
19 Correct 93 ms 19328 KB Output is correct
20 Correct 99 ms 19308 KB Output is correct
21 Correct 84 ms 19268 KB Output is correct
22 Correct 73 ms 18540 KB Output is correct
23 Correct 70 ms 18028 KB Output is correct
24 Correct 75 ms 17900 KB Output is correct
25 Correct 68 ms 18668 KB Output is correct
26 Correct 76 ms 19180 KB Output is correct
27 Correct 103 ms 19308 KB Output is correct
28 Correct 78 ms 19308 KB Output is correct
29 Correct 86 ms 19456 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14572 KB Output is correct
2 Correct 11 ms 14572 KB Output is correct
3 Correct 12 ms 14572 KB Output is correct
4 Correct 12 ms 14700 KB Output is correct
5 Correct 12 ms 14572 KB Output is correct
6 Correct 12 ms 14572 KB Output is correct
7 Correct 12 ms 14572 KB Output is correct
8 Correct 12 ms 14572 KB Output is correct
9 Correct 11 ms 14572 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 13 ms 14572 KB Output is correct
12 Correct 11 ms 14572 KB Output is correct
13 Correct 12 ms 14572 KB Output is correct
14 Correct 29 ms 15708 KB Output is correct
15 Correct 48 ms 16880 KB Output is correct
16 Correct 71 ms 18284 KB Output is correct
17 Correct 117 ms 19308 KB Output is correct
18 Correct 101 ms 19308 KB Output is correct
19 Correct 93 ms 19328 KB Output is correct
20 Correct 99 ms 19308 KB Output is correct
21 Correct 84 ms 19268 KB Output is correct
22 Correct 73 ms 18540 KB Output is correct
23 Correct 70 ms 18028 KB Output is correct
24 Correct 75 ms 17900 KB Output is correct
25 Correct 68 ms 18668 KB Output is correct
26 Correct 76 ms 19180 KB Output is correct
27 Correct 103 ms 19308 KB Output is correct
28 Correct 78 ms 19308 KB Output is correct
29 Correct 86 ms 19456 KB Output is correct
30 Correct 287 ms 28760 KB Output is correct
31 Correct 338 ms 32100 KB Output is correct
32 Correct 436 ms 34020 KB Output is correct
33 Correct 635 ms 41820 KB Output is correct
34 Correct 197 ms 28264 KB Output is correct
35 Correct 607 ms 41672 KB Output is correct
36 Correct 611 ms 41660 KB Output is correct
37 Correct 605 ms 41436 KB Output is correct
38 Correct 568 ms 41564 KB Output is correct
39 Correct 585 ms 41436 KB Output is correct
40 Correct 479 ms 41308 KB Output is correct
41 Correct 633 ms 41436 KB Output is correct
42 Correct 603 ms 41436 KB Output is correct
43 Correct 347 ms 35420 KB Output is correct
44 Correct 367 ms 35932 KB Output is correct
45 Correct 355 ms 37212 KB Output is correct
46 Correct 417 ms 33884 KB Output is correct
47 Correct 418 ms 31068 KB Output is correct
48 Correct 457 ms 37468 KB Output is correct
49 Correct 423 ms 37596 KB Output is correct