#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
