Submission #555732

#	Time	Username	Problem	Language	Result	Execution time	Memory
555732		Jarif_Rahman	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	330 ms	46668 KiB

fortune_telling2

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct sparse_table{
    vector<int> lg;
    vector<vector<int>> v;
    sparse_table(vector<int> _v){
        int n = _v.size();
        lg.resize(n+1);
        for(int i = 0; i <= n; i++) lg[i] = log2(i);
        int k = 0, p = 1;
        while(p < n) p*=2, k++;
        k++;
        v = vector<vector<int>>(n, vector<int>(k, 0));
        for(int i = 0; i < n; i++) v[i][0] = _v[i];
        for(int p = 1; p < k; p++){
            for(int i = 0; i < n; i++){
                v[i][p] = max(v[i][p], v[i][p-1]);
                if(i + (1<<(p-1)) < n) v[i][p] = max(v[i][p], v[i + (1<<(p-1))][p-1]);
            }
        }
    }
    int query(int a, int b){
        int p = lg[b-a+1];
        return max(v[a][p], v[b-(1<<p)+1][p]);
    }
};
 

struct BIT{
    int n;
    vector<int> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, int x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    int sum(int in){
        in++;
        int s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    int sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k; cin >> n >> k;

    vector<ll> A(n), B(n);
    vector<pair<ll, int>> T(k);

    for(int i = 0; i < n; i++) cin >> A[i] >> B[i];
    for(int i = 0; i < k; i++) cin >> T[i].f, T[i].sc = i;

    sort(T.begin(), T.end());
    vector<int> _T;
    for(int i = 0; i < k; i++) _T.pb(T[i].sc);

    sparse_table sp(_T);

    ll ans = 0;
    vector<vector<pair<int, int>>> sth(k);

    for(int i = 0; i < n; i++){
        auto it1 = lower_bound(T.begin(), T.end(), make_pair(min(A[i], B[i]), -1));
        auto it2 = lower_bound(T.begin(), T.end(), make_pair(max(A[i], B[i]), -1));

        if(it1 == it2){
            ans+=(T.end()-it2)%2?B[i]:A[i];
            continue;
        }
        if(it2 == T.end()){
            ans+=max(A[i], B[i]);
            continue;
        }

        sth[it2-T.begin()].pb({i, sp.query(it1-T.begin(), it2-T.begin()-1)});
    }

    BIT bit(k);

    for(int i = k-1; i >= 0; i--){
        bit.add(T[i].sc, 1);
        for(auto [in, x]: sth[i]) ans+=bit.sum(x, k-1)%2?min(A[in], B[in]):max(A[in], B[in]);
    }

    cout << ans << "\n";
}

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