Submission #619699

#	Time	Username	Problem	Language	Result	Execution time	Memory
619699		Ahmadsm2005	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	1 ms	340 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];
bool Z[200000];
vector<pair<int,int>>KS;
set<int>SPP;
bool COMP(pair<int,int>A,pair<int,int>B){
    return max(A.first,A.second) > max(B.first,B.second);
}
int RMQ(int L,int R){
    int MX = -1;
    for(int i = L ; i <= R; i += 1)MX = max(MX,KK[i]);
    return MX;
}
int32_t main()
{
    cin.tie(0),iostream::sync_with_stdio(0);
    ordered_set X;
    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});
    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;
                auto itr = SPP.lower_bound(idx);
                int R = (*itr);
                itr--;
                int L = (*itr);
                L++,R--;
                X.erase(X.upper_bound(RMQ(L,R)));
                if(RMQ(L,idx - 1) != -1)X.insert(RMQ(L,idx - 1));
                if(RMQ(idx + 1,R) != -1)X.insert(RMQ(idx + 1,R));
                SPP.insert(idx);
                CNT++;
                KS.pop_back();
            }
            else break;
        }
        if(SP[i].first > SP[i].second){
            auto itr = SPP.lower_bound(0);
            int Z = ((X.size() - X.order_of_key(SP[i].second - 1)) + CNT + ((RMQ(0,(*itr) - 1)) >= SP[i].second)) % 2;
            if(Z % 2 == 0)ANS += SP[i].first;
            else ANS += SP[i].second;
        }
        else{
            int Z = ((X.size() - X.order_of_key(SP[i].first - 1)) + CNT) % 2;
            if(Z % 2 == 0)ANS += SP[i].first;
            else ANS += SP[i].second;
        }
    }
    cout<<ANS;
}

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