#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
const int uMX = 600006;
int n, k;
int a[MX], b[MX];
int ops[MX];
map<int,int>HASH, iHASH;
vector<int>mst[MX*4], imst(uMX*4);
//mst ->index to value
//imst ->value to index
//HASH ->HASH value of some bigger value
//iHASH ->index of some HASH value
vector<int>merge(vector<int>A, vector<int>B) {
vector<int>ret;
int p = 0, q = 0;
int N = A.size(), M = B.size();
while(p<N && q<M) {
if(A[p]<B[q]) {
ret.push_back(A[p++]);
} else {
ret.push_back(B[q++]);
}
}
while(p<N) ret.push_back(A[p++]);
while(q<M) ret.push_back(B[q++]);
return ret;
}
void Build(int l, int r, int v) { //mst
if(l==r) {
mst[v].push_back(ops[l]);
return;
}
int m = (l+r)/2;
Build(l, m, v*2);
Build(m+1, r, v*2+1);
mst[v] = merge(mst[v*2], mst[v*2+1]);
}
void Build2(int l, int r, int v) { //imst
if(l==r) {
if(iHASH.count(l)) {
imst[v] = iHASH[l];
} else {
imst[v] = -1;
}
return;
}
int m = (l+r)/2;
Build2(l, m, v*2);
Build2(m+1, r, v*2+1);
imst[v] = max(imst[v*2], imst[v*2+1]);
}
int q2(int l, int r, int L, int R, int v) {
if(l>=L && r<=R) {
return imst[v];
} else if(l>R || r<L) return -1;
int m = (l+r)/2;
return max(q2(l, m, L, R, v*2), q2(m+1, r, L, R, v*2+1));
}
int q(int l, int r, int L, int R, int lb, int v) {
if(l>=L && r<=R) {
return mst[v].end()-lower_bound(mst[v].begin(), mst[v].end(), lb);
}
if(l>R || r<L) return 0;
int m = (l+r)/2;
return q(l, m, L, R, lb, v*2) + q(m+1, r, L, R, lb, v*2+1);
}
void PlayGround() {
cin >> n >> k;
for(int i=1; i<=n; ++i) {
cin >> a[i] >> b[i];
HASH[a[i]] = HASH[b[i]] = 0;
}
for(int i=1; i<=k; ++i) {
cin >> ops[i];
HASH[ops[i]] = i;
}
int tag = 1;
for(auto &p : HASH) {
if(p.second) iHASH[tag] = p.second;
p.second = tag++;
} //end of HASH stuffs
Build(1, k, 1);
Build2(1, uMX-1, 1);
//final processing
long long ans = 0;
for(int i=1; i<=n; ++i) {
if(a[i]==b[i]) {
ans += a[i];
continue;
}
int mx = a[i], mn = b[i];
if(mx<mn) swap(mx, mn);
int yellow = q2(1, uMX-1, HASH[mn], HASH[mx]-1, 1);
int l;
if(yellow==-1) l = 1;
else l = yellow+1;
int cnt = q(1, k, l, k, HASH[mx], 1);
if(yellow==-1) {
ans += (cnt&1)?b[i]:a[i];
} else {
ans += (cnt&1)?mn:mx;
}
}
cout << ans << endl;
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
28640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
28640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
28640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
