oj.uz

Submission #411254

# Submission time Handle Problem Language Result Execution time Memory
411254 2021-05-24T20:35:59 Z AlperenT Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 469 ms 45560 KB 
#include <bits/stdc++.h>

using namespace std;

const long long N = 3e5 + 5;

long long n, k, t[N], ans, tindx[N * 2], indx, cnt;

priority_queue<pair<long long, long long>> pq;

struct Card{
    long long a, b, aa, bb;
    bool swapped;

    bool operator < (Card &scnd) const{
        return a > scnd.a;
    }
};

Card cards[N];

struct SegTree{
    long long tree[(N * 2) * 4];

    void build(long long v, long long l, long long r){
        if(l == r) tree[v] = tindx[l];
        else{
            long long m = l + (r - l) / 2;
            build(v * 2, l, m);
            build(v * 2 + 1, m + 1, r);
            tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
        } 
    }

    long long query(long long v, long long tl, long long tr, long long l, long long r){
        if(l > r) return 0;
        else if(tl == l && tr == r) return tree[v];
        else{
            long long tm = tl + (tr - tl) / 2;
            return max(query(v * 2, tl, tm, l, min(tm, r)), query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
        }
    }
};

SegTree segtree;

struct Fenwick{
    long long tree[N * 2];

    long long getsum(long long r){
        long long sum = 0;
        for(long long i = r; i >= 1; i -= i & (-i)){
            sum += tree[i];
        }
        return sum;
    }

    long long query(long long l, long long r){
        return getsum(r) - getsum(l - 1);
    }

    void update(long long pos, long long val){
        for(long long i = pos; i < N * 2; i += i & (-i)){
            tree[i] += val;
        }
    }
};

Fenwick fw;

void compress(){
    vector<long long> nums;

    for(long long i = 1; i <= n; i++) nums.push_back(cards[i].a), nums.push_back(cards[i].b);
    for(long long i = 1; i <= k; i++) nums.push_back(t[i]);

    sort(nums.begin(), nums.end());

    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    for(long long i = 1; i <= n; i++){
        cards[i].aa = cards[i].a;
        cards[i].a = lower_bound(nums.begin(), nums.end(), cards[i].a) - nums.begin() + 1;
        cards[i].bb = cards[i].b;
        cards[i].b = lower_bound(nums.begin(), nums.end(), cards[i].b) - nums.begin() + 1;
    }

    for(long long i = 1; i <= k; i++) t[i] = lower_bound(nums.begin(), nums.end(), t[i]) - nums.begin() + 1;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    
    cin >> n >> k;

    for(long long i = 1; i <= n; i++){
        cin >> cards[i].a >> cards[i].b;

        if(cards[i].b > cards[i].a) swap(cards[i].a, cards[i].b), cards[i].swapped = true;
    }

    for(long long i = 1; i <= k; i++) cin >> t[i];

    compress();

    sort(cards + 1, cards + n + 1);

    for(long long i = 1; i <= k; i++){
        pq.push({t[i], i});

        tindx[t[i]] = max(tindx[t[i]], i);
    }

    segtree.build(1, 1, N * 2);

    for(long long i = 1; i <= n; i++){
        while(!pq.empty() && pq.top().first >= cards[i].a){
            fw.update(pq.top().second, 1);
            pq.pop();
        }

        indx = segtree.query(1, 1, N * 2, cards[i].b, cards[i].a - 1);
        cnt = fw.query(indx + 1, N * 2);

        if(indx == 0){
            if(cards[i].swapped) ans += (cnt % 2 == 0 ? cards[i].bb : cards[i].aa);
            else ans += (cnt % 2 == 0 ? cards[i].aa : cards[i].bb);
        }
        else{
            ans += (cnt % 2 == 0 ? cards[i].aa : cards[i].bb);
        }
    }

    cout << ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16844 KB Output is correct
2 Correct 12 ms 16840 KB Output is correct
3 Correct 12 ms 16908 KB Output is correct
4 Correct 12 ms 16844 KB Output is correct
5 Correct 12 ms 16924 KB Output is correct
6 Correct 13 ms 16876 KB Output is correct
7 Correct 13 ms 16908 KB Output is correct
8 Correct 13 ms 16844 KB Output is correct
9 Correct 12 ms 16852 KB Output is correct
10 Correct 12 ms 16880 KB Output is correct
11 Correct 12 ms 16844 KB Output is correct
12 Correct 12 ms 16844 KB Output is correct
13 Correct 12 ms 16844 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16844 KB Output is correct
2 Correct 12 ms 16840 KB Output is correct
3 Correct 12 ms 16908 KB Output is correct
4 Correct 12 ms 16844 KB Output is correct
5 Correct 12 ms 16924 KB Output is correct
6 Correct 13 ms 16876 KB Output is correct
7 Correct 13 ms 16908 KB Output is correct
8 Correct 13 ms 16844 KB Output is correct
9 Correct 12 ms 16852 KB Output is correct
10 Correct 12 ms 16880 KB Output is correct
11 Correct 12 ms 16844 KB Output is correct
12 Correct 12 ms 16844 KB Output is correct
13 Correct 12 ms 16844 KB Output is correct
14 Correct 27 ms 18024 KB Output is correct
15 Correct 45 ms 19180 KB Output is correct
16 Correct 65 ms 20096 KB Output is correct
17 Correct 85 ms 21568 KB Output is correct
18 Correct 84 ms 21512 KB Output is correct
19 Correct 84 ms 21552 KB Output is correct
20 Correct 84 ms 21488 KB Output is correct
21 Correct 77 ms 21516 KB Output is correct
22 Correct 62 ms 21184 KB Output is correct
23 Correct 63 ms 21116 KB Output is correct
24 Correct 64 ms 20880 KB Output is correct
25 Correct 62 ms 21272 KB Output is correct
26 Correct 62 ms 20860 KB Output is correct
27 Correct 72 ms 21172 KB Output is correct
28 Correct 66 ms 21264 KB Output is correct
29 Correct 73 ms 21396 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16844 KB Output is correct
2 Correct 12 ms 16840 KB Output is correct
3 Correct 12 ms 16908 KB Output is correct
4 Correct 12 ms 16844 KB Output is correct
5 Correct 12 ms 16924 KB Output is correct
6 Correct 13 ms 16876 KB Output is correct
7 Correct 13 ms 16908 KB Output is correct
8 Correct 13 ms 16844 KB Output is correct
9 Correct 12 ms 16852 KB Output is correct
10 Correct 12 ms 16880 KB Output is correct
11 Correct 12 ms 16844 KB Output is correct
12 Correct 12 ms 16844 KB Output is correct
13 Correct 12 ms 16844 KB Output is correct
14 Correct 27 ms 18024 KB Output is correct
15 Correct 45 ms 19180 KB Output is correct
16 Correct 65 ms 20096 KB Output is correct
17 Correct 85 ms 21568 KB Output is correct
18 Correct 84 ms 21512 KB Output is correct
19 Correct 84 ms 21552 KB Output is correct
20 Correct 84 ms 21488 KB Output is correct
21 Correct 77 ms 21516 KB Output is correct
22 Correct 62 ms 21184 KB Output is correct
23 Correct 63 ms 21116 KB Output is correct
24 Correct 64 ms 20880 KB Output is correct
25 Correct 62 ms 21272 KB Output is correct
26 Correct 62 ms 20860 KB Output is correct
27 Correct 72 ms 21172 KB Output is correct
28 Correct 66 ms 21264 KB Output is correct
29 Correct 73 ms 21396 KB Output is correct
30 Correct 159 ms 25224 KB Output is correct
31 Correct 216 ms 31516 KB Output is correct
32 Correct 289 ms 34196 KB Output is correct
33 Correct 469 ms 45492 KB Output is correct
34 Correct 108 ms 26628 KB Output is correct
35 Correct 452 ms 45496 KB Output is correct
36 Correct 453 ms 45500 KB Output is correct
37 Correct 452 ms 45536 KB Output is correct
38 Correct 419 ms 45460 KB Output is correct
39 Correct 438 ms 45484 KB Output is correct
40 Correct 393 ms 45296 KB Output is correct
41 Correct 416 ms 45560 KB Output is correct
42 Correct 416 ms 45496 KB Output is correct
43 Correct 268 ms 41044 KB Output is correct
44 Correct 262 ms 41316 KB Output is correct
45 Correct 275 ms 42488 KB Output is correct
46 Correct 303 ms 41172 KB Output is correct
47 Correct 290 ms 40380 KB Output is correct
48 Correct 341 ms 43948 KB Output is correct
49 Correct 326 ms 44108 KB Output is correct