Submission #1272826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272826		DeathIsAwe	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	378 ms	11180 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
int movesdone[524288];
int maxseg[524288];
vector<int> moves(200000);
vector<pair<int,int>> cards(200000);
vector<pair<int,int>> moveindex;


void maxupdate(int pos, int val) {
    pos += 262144;
    maxseg[pos] = val;
    while (pos != 1) {
        pos /= 2;
        maxseg[pos] = max(maxseg[pos * 2 + 1], maxseg[pos * 2]);
    }
}


int maxfind(int l, int r) {
    l += 262144; r += 262144;
    int val = 0;
    while (l <= r) {
        if (l % 2 == 1) val = max(val, maxseg[l++]);
        if (r % 2 == 0) val = max(val, maxseg[r--]);
        l /= 2; r /= 2;
    }
    return val;
}


void update(int pos) {
    pos += 262144;
    movesdone[pos] = 1;
    while (pos != 1) {
        pos /= 2;
        movesdone[pos] = movesdone[pos * 2 + 1] + movesdone[pos * 2];
    }
}


int find(int l, int r) {
    l += 262144; r += 262144;
    int val = 0;
    while (l <= r) {
        if (l % 2 == 1) val += movesdone[l++];
        if (r % 2 == 0) val += movesdone[r--];
        l /= 2; r /= 2;
    }
    return val;
}


bool comp(int a, int b) {
    return max(cards[a].ff, cards[a].ss) > max(cards[b].ff, cards[b].ss);
}


int main() {
    for (int i=0;i<524288;i++) {
        movesdone[i] = 0;
        maxseg[i] = 0;
    } 


    int n, k; cin >> n >> k;
    for (int i=0;i<n;i++) {
        cin >> cards[i].ff >> cards[i].ss;
    }
    for (int i=0;i<k;i++) {
        cin >> moves[i];
        moveindex.pb(mp(moves[i], i));
        maxupdate(i, moves[i]);
    }
    sort(moveindex.begin(), moveindex.end());


    vector<int> queries(n);
    vector<int> order;
    for (int i=0;i<n;i++) {order.pb(i);}
    sort(order.begin(), order.end(), comp);
    int curmax = k;
    for (int i: order) {
        if (cards[i].ff == cards[i].ss) {
            queries[i] = -1; continue;
        }
        while (curmax) {
            if (moveindex[curmax - 1].ff >= max(cards[i].ff, cards[i].ss)) {
                maxupdate(moveindex[curmax - 1].ss, 0);
                curmax -= 1;
            } else break;
        }
        int top = k, bottom = -1, mid;
        while (top > bottom + 1) {
            mid = (top + bottom) / 2;
            if (maxfind(mid, k - 1) >= min(cards[i].ff, cards[i].ss)) {
                bottom = mid;
            } else {
                top = mid;
            }
        }
        queries[i] = bottom;
    }
    //for (int i=0;i<n;i++) {
    //    cout << order[i] << ' ' << queries[order[i]] << '\n';
    //}
    

    ll ans = 0;
    curmax = k;
    for (int i: order) {
        while (curmax) {
            if (moveindex[curmax - 1].ff >= max(cards[i].ff, cards[i].ss)) {
                update(moveindex[curmax - 1].ss);
                curmax -= 1;
            } else break;
        }
        int flips = find(queries[i] + 1, k - 1);
        //cout << i << ' ' << flips << '\n';
        if (queries[i] == -1) {
            if (flips % 2 == 1) ans += cards[i].ss;
            else ans += cards[i].ff;
        } else if (cards[i].ff > cards[i].ss) {
            if (flips % 2 == 1) ans += cards[i].ss;
            else ans += cards[i].ff;
        } else {
            if (flips % 2 == 1) ans += cards[i].ff;
            else ans += cards[i].ss;
        }
    }
    cout << ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65