#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){
if(seg[idx] >= v)return LL;
else return LL - 1;
}
else if(seg[idx * 2 + 2] >= v)return query(v,(LL + RR) / 2 + 1,RR,idx * 2 + 2);
return query(v,LL,(LL + RR) / 2, idx * 2 + 1);
}
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}),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;
int R = (SPP.size() - SPP.order_of_key(F) + (SP[i].first < SP[i].second)) % 2;
ANS += (R?SP[i].first:SP[i].second);
}
cout<<ANS;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
