oj.uz

답안 #619645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
619645 2022-08-02T14:00:10 Z Ahmadsm2005 운세 보기 2 (JOI14_fortune_telling2) C++17
0 / 100
 1 ms 340 KB 
#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<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());
    X.insert(RMQ(0,K - 1));
    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(RMQ(L,R));
                X.insert(RMQ(L,idx - 1));
                X.insert(RMQ(idx + 1,R));
                //cout<<L+1<<' '<<R<<endl;
                SPP.insert(idx);
                CNT++;
                KS.pop_back();
            }
            else break;
        }
        if(SP[i].first > SP[i].second){
            auto itr = SPP.lower_bound(0);
            //cout<<max(SP[i].first,SP[i].second)<<' '<<RMQ(0,(*itr)-1)<<' '<<X.size() - X.order_of_key(SP[i].second)<<endl;
            int Z = ((X.size() - X.order_of_key(SP[i].second)) + 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].second)) + CNT) % 2;
            if(Z % 2 == 0)ANS += SP[i].first;
            else ANS += SP[i].second;
        }
        //cout<<ANS<<' ';
    }
    cout<<ANS;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -