Submission #619958

#	Time	Username	Problem	Language	Result	Execution time	Memory
619958		Ahmadsm2005	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	454 ms	33764 KiB

fortune_telling2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef tree<
int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int N,K,A[200000],B[200000],KK[200000],seg[800000];
bool Z[200000];
vector<pair<int,int>>KS;
ordered_set SPP;
bool COMP(pair<int,int>A,pair<int,int>B){
    return max(A.first,A.second) > max(B.first,B.second);
}
void UPD(int T, int v, int L = 0, int R = 200000, int idx = 0){
    if(L == R && L == T){seg[idx] = v;return;}
    else if(L > T || R < T)return;
    UPD(T,v,L,(L + R) / 2,idx * 2 + 1);
    UPD(T,v,(L + R) / 2 + 1, R, idx * 2 + 2);
    seg[idx] = max(seg[idx * 2 + 1], seg[idx * 2 + 2]);
}
int query(int v,int LL = 0, int RR = 200000, int idx = 0){
    if(LL == RR){
        return LL;
    }
    else if(seg[idx * 2 + 2] >= v)return query(v,(LL + RR) / 2 + 1,RR,idx * 2 + 2);
    else if(seg[idx * 2 + 1] >= v)return query(v,LL,(LL + RR) / 2, idx * 2 + 1);
    return -1;
}
int32_t main()
{
    cin.tie(0),iostream::sync_with_stdio(0);
    cin>>N>>K;
    for(int i = 0; i < N; i += 1){
        cin>>A[i]>>B[i];
    }
    SPP.insert(-1),SPP.insert(K);
    for(int i = 0; i < K; i += 1)cin >> KK[i],KS.push_back({KK[i],i}),UPD(i,KK[i]);
    vector<pair<int,int>>SP;
    for(int i = 0; i < N; i += 1)SP.push_back({A[i],B[i]});
    sort(SP.begin(),SP.end(),COMP);
    sort(KS.begin(),KS.end());
    int CNT = 0,ANS = 0;
    for(int i = 0; i < N; i += 1){
        int MX = max(SP[i].first,SP[i].second);
        while(KS.size()){
            if(KS.back().first >= MX){
                int idx = KS.back().second;
                UPD(idx,0);
                SPP.insert(idx);
                CNT++;
                KS.pop_back();
            }
            else break;
        }
        int F = query(min(SP[i].first,SP[i].second));
        //cout<<"lol: "<<F<<endl;
        if(F + 1){
            int R = (SPP.size() - SPP.order_of_key(F) + (SP[i].first < SP[i].second)) % 2;
            ANS += (R?SP[i].first:SP[i].second);
        }
        else{
            //cout<<(((SP[i].first < SP[i].second) + CNT + 1) % 2)<<endl;
            ANS += (((CNT + 1) % 2)?SP[i].first:SP[i].second);
        }
    }
    cout<<ANS;
}

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