Submission #971415

#	Time	Username	Problem	Language	Result	Execution time	Memory
971415		Whisper	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	434 ms	59264 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define All(a...) a.begin(), a.end()

const int MAX = 6e5 + 5;
int nArr, numQuery;
pair<int, int> A[MAX];
int qs[MAX];
vector<int> comp;

int find(int x){
    return lower_bound(All(comp), x) - comp.begin() + 1;
}
int st[MAX << 2], F[MAX];

void Modify(int nd, int l, int r, int pos, int val){
    if (pos < l || pos > r) return;
    if(l == r){
        st[nd] = max(st[nd], val);
        return;
    }
    int mid = (l + r) >> 1;
    Modify(nd << 1, l, mid, pos, val);
    Modify(nd << 1 | 1, mid + 1, r, pos, val);
    st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
}
int Query(int nd, int l, int r, int u, int  v){
    if (u > r || v < l) return 0;
    if (u <= l && v >= r) return st[nd];
    int mid = (l + r) >> 1;
    int ql = Query(nd << 1, l, mid, u, v);
    int qr = Query(nd << 1 | 1, mid + 1, r, u, v);
    return max(ql, qr);
}

void Modify(int pos, int val){ Modify(1, 1, comp.size(), pos, val); }
int Query(int l, int r){ return Query(1, 1, comp.size(), l, r); }

void upd(int p, int val){
    for (; p <= (int)comp.size(); p += p & (-p)) F[p] += val;
}
int get(int p){
    int res = 0;
    for (; p > 0; p -= p & (-p)) res += F[p];
    return res;
}

vector<int> event[MAX];

void Whisper(){
    cin >> nArr >> numQuery;
    for (int i = 1; i <= nArr; ++i){
        cin >> A[i].first >> A[i].second;
        comp.push_back(A[i].first);
        comp.push_back(A[i].second);
    }

    for (int i = 1; i <= numQuery; ++i){
        cin >> qs[i];
        comp.push_back(qs[i]);
    }
    sort(All(comp));
    comp.resize(unique(All(comp)) - comp.begin());
    for (int i = 1; i <= numQuery; ++i){
        Modify(find(qs[i]), i);
    }
    int ans = 0;
    for (int i = 1; i <= nArr; ++i){
        int l = find(min(A[i].first, A[i].second));
        int r = find(max(A[i].first, A[i].second));
        if (l == r){
            ans += A[i].first; continue;
        }
        int mx_id = Query(l, r - 1);
        event[mx_id].emplace_back(i);
    }

    for (int i = numQuery; i >= 1; --i){
        for (int &j : event[i]){
            int v = find(max(A[j].first, A[j].second));
            int turn = get((int)comp.size()) - get(v - 1);
            if(turn & 1) {
                ans += min(A[j].first, A[j].second);
            }
            else{
                ans += max(A[j].first, A[j].second);
            }
        }
        upd(find(qs[i]), 1);
    }

    for (int &j : event[0]){
        int v = find(max(A[j].first, A[j].second));
        int turn = get((int)comp.size()) - get(v - 1);
        if (turn & 1) ans += A[j].second;
        else ans += A[j].first;
    }

    cout << ans;
    /*
        Case 1: if A(i).first <= qs(j) < A(i).second
        -> the answer always = A(i).second
        Case 2: if qs(j) > A(i).second
        -> the cards is always turn down
        Case 3: if qs(j) < A(i).first
        -> The cards isn't affected
    */
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

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