#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for (int i=(a); i>=(b); --i)
#define pb push_back
#define pf push_front
#define mp make_pair
#define TWO(x) (1<<(x))
#define BIT(s,i) (((s)&TWO(i))>0)
#define ON(s,i) (s |= TWO(i))
#define OFF(s,i) (s &= ~TWO(i))
#define FLIP(s,i) (s ^= TWO(i))
#define vvec vector<vector<int>>
struct ngocon{
int val,lazy;
};
struct point{
int x,y;
};
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> pipi;
const int h4[4] = {1,0,-1,0}; /// 4 huong
const int c4[4] = {0,1,0,-1}; /// 4 huong
const int h8[8] = {-1,-1,-1,0,1,1,1,0}; /// 8 huong
const int c8[8] = {-1,0,1,1,1,0,-1,-1}; /// 8 huong
const int cv1[8] = {1,2,2,1,-1,-2,-2,-1}; /// 8 huong quan ma
const int cv2[8] = {-2,-1,1,2,2,1,-1,-2}; /// 8 huong quan ma
const int mod = 1e9 + 7; /// chia du
const int base = 26; /// ma hoa
const int oo = 1e16;
const int N = 2e5 + 2;
int n,k,result;
int a[N],b[N],v[N],f[24*N],d[N],bit[6*N],ans[N];
bool dd[N];
vector <int> nor,vec[N];
unordered_map <int,int> Map;
void compress(){
FOR(i,1,n) nor.pb(a[i]), nor.pb(b[i]);
FOR(i,1,k) nor.pb(v[i]);
sort(nor.begin(),nor.end());
int pos;
FOR(i,1,n){
pos = lower_bound(nor.begin(),nor.end(),a[i]) - nor.begin() + 1;
Map[pos] = a[i]; a[i] = pos;
pos = lower_bound(nor.begin(),nor.end(),b[i]) - nor.begin() + 1;
Map[pos] = b[i]; b[i] = pos;
}
FOR(i,1,k) v[i] = lower_bound(nor.begin(),nor.end(),v[i]) - nor.begin() + 1;
}
void update(int i, int l, int r, int u, int v){
if (r < u || u < l) return;
if (l == r){
f[i] = max(f[i],v);
return;
}
int mid = (l + r) >> 1;
update(i*2,l,mid,u,v);
update(i*2+1,mid+1,r,u,v);
f[i] = max(f[i*2],f[i*2+1]);
}
int query(int i, int l, int r, int u, int v){
if (r < u || v < l || u > v) return 0;
if (u <= l && r <= v) return f[i];
int mid = (l + r) >> 1;
return max(query(i*2,l,mid,u,v),query(i*2+1,mid+1,r,u,v));
}
void update_bit(int i, int v){
while (i <= 6*n){
bit[i] += v;
i += (i & (-i));
}
}
int query_bit(int i){
int res = 0;
while (i > 0){
res += bit[i];
i -= (i & (-i));
}
return res;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("input.txt","r",stdin);
//freopen("ac.txt","w",stdout);
cin >> n >> k;
FOR(i,1,n) cin >> a[i] >> b[i];
FOR(i,1,k) cin >> v[i];
compress();
// FOR(i,1,n) cout << a[i] << ' ' << b[i] << '\n';
// FOR(i,1,k) cout << v[i] << ' '; cout << '\n';
FOR(i,1,k){
update(1,1,6*n,v[i],i);
update_bit(v[i],1);
}
// cout << "end update" << '\n';
FOR(i,1,n){
// cout << i << ": " << min(a[i],b[i]) << ' ' << max(a[i],b[i]) - 1 << '\n';
d[i] = query(1,1,6*n,min(a[i],b[i]),max(a[i],b[i]) - 1);
if (d[i] != 0) dd[i] = 1;
vec[d[i]+1].pb(i);
}
// cout << "mmb" << '\n';
//
// FOR(i,1,n) cout << d[i] << ' '; cout << '\n';
FOR(i,1,k){
// cout << i << '\n';
for (auto j : vec[i]) ans[j] = k - i + 1 - query_bit(b[j] - 1);
update_bit(v[i],-1);
}
// cout << "ans: "; FOR(i,1,n) cout << ans[i] << ' '; cout << '\n';
FOR(i,1,n){
a[i] = Map[a[i]];
b[i] = Map[b[i]];
}
FOR(i,1,n){
if (!dd[i]){
if (ans[i]%2 == 0) result += a[i];
else result += b[i];
}
else{
if (a[i] >= b[i]){
if (ans[i]%2 == 0) result += a[i];
else result += b[i];
}
else{
if (ans[i]%2 == 0) result += b[i];
else result += a[i];
}
}
}
cout << result;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
