#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 2e5+10;
const int MX2 = (1<<19);
const lint LNF = 2e18;
/*
Ci = max(Ai, Bi), Di = min(Ai, Bi)
Ci 오름차순으로 카드 정렬. Seg1, Seg2 관리
Seg1에는 T가 Ci 미만인 연산들이 T를 키, 인덱스가 밸류. (Di 이상인지만 물어보므로 Ai로 좌표압축)
Seg2에는 T가 Ci 이상인 연산들이 인덱스가 키, 개수가 밸류
// 알아서 세그 관리
int x = Seg1.get(A[i]); // 키가 Ai 이상인 것들 중 최대 밸류
int y = Seg2.get(x); // 키가 x이상인 것들 밸류 합
if(x<=0) ans += (y%2 ? 나중거 : 처음거)
else ans += (y%2 ? 작은거 : 큰거)
*/
const int _max(int a, int b){ return a>b ? a : b; }
class Crd_t{
vector<int> P;
public:
void add(int p){
P.push_back(p);
}
int compress(){
sort(P.begin(), P.end());
int sz = unique(P.begin(), P.end()) - P.begin();
P.resize(sz);
return sz;
}
int get_hi(int x){
return lower_bound(P.begin(), P.end(), x) - P.begin() + 1;
}
int get(int x){
if(!binary_search(P.begin(), P.end(), x)){ cerr<<"SHIT\n"; exit(42); }
return get_hi(x);
}
} Crd;
class Seg1_t{
// max
vector<int> T;
int n;
void add(int v, int s, int e, int p, int x){
T[v] = _max(T[v], x);
if(s==e) return;
int mid = (s+e)/2;
if(p<=mid) add(v*2,s,mid,p,x);
else add(v*2+1,mid+1,e,p,x);
}
int get(int v, int s, int e, int l){
if(l<=s) return T[v];
if(e<l) return 0;
return _max(get(v*2,s,(s+e)/2,l), get(v*2+1,(s+e)/2+1,e,l));
}
public:
void init(int sz){
n = sz;
T.resize(MX2, 0);
}
void add(int x, int val){
x = Crd.get_hi(x);
add(1,1,n,x,val);
}
int get(int x){
x = Crd.get(x);
return get(1,1,n,x);
}
} Seg1;
class Seg2_t{
// sum
vector<int> T;
int n;
void add(int v, int s, int e, int p, int x){
T[v]++;
if(s==e) return;
int mid = (s+e)/2;
if(p<=mid) add(v*2,s,mid,p,x);
else add(v*2+1,mid+1,e,p,x);
}
int get(int v, int s, int e, int l){
if(l<=s) return T[v];
if(e<l) return 0;
return get(v*2,s,(s+e)/2,l) + get(v*2+1,(s+e)/2+1,e,l);
}
public:
void init(int sz){
n = sz;
T.resize(MX2, 0);
}
void add(int idx, int val){
add(1,1,n,idx,val);
}
int get(int x){
return get(1,1,n,x);
}
} Seg2;
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, k; cin>>n>>k;
static int A[MAX], B[MAX];
vector<pii> P, Q;
for(int i=1; i<=n; i++){
int a, b; cin>>a>>b;
A[i] = a, B[i] = b;
P.push_back({max(a,b), i});
Crd.add(min(a,b));
}
for(int i=1; i<=k; i++){
int t; cin>>t;
Q.push_back({t, i});
}
sort(Q.begin(), Q.end());
sort(P.begin(), P.end());
Crd.add(INF);
int sz = Crd.compress();
Seg1.init(sz); Seg2.init(k);
// max, sum
for(pii q:Q){
int t,i; tie(t,i) = q;
Seg2.add(i, 1);
}
lint ans = 0;
for(pii p:P){
int c,i; tie(c,i) = p;
static int frt = 0;
while(frt<k && Q[frt].first < c){
int t,j; tie(t,j) = Q[frt++];
Seg2.add(j, -1);
Seg1.add(t, j);
}
int d = min(A[i], B[i]);
int x = Seg1.get(d);
int y = Seg2.get(x);
if(x<=0) ans += (y%2 ? B[i] : A[i]);
else ans += (y%2 ? d : c);
}
cout<<ans<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
