#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
#define ff first
#define ss second
const int N = 2e5 + 5;
const ll inf = 1e17 + 100;
int n, k, a[N], b[N], t[N], id[N];
int st[3*N][20], root[3*N];
map <int,int> m;
set <int> s;
vector <int> adj[3*N], L, R, value;
int maxi(int l, int r){
int log = 31 - __builtin_clz(r-l+1);
return max(st[l][log], st[r - (1<<log) + 1][log]);
}
int createleaf(int x){
L.push_back(-1), R.push_back(-1);
value.push_back(x);
return L.size() - 1;
}
int createvertex(int u, int v){
L.push_back(u), R.push_back(v);
value.push_back(value[u] + value[v]);
return L.size() - 1;
}
int build(int l, int r){
if(l == r) return createleaf(0);
int m = (l+r)>>1;
return createvertex(build(l, m), build(m+1, r));
}
int upd(int id, int l, int r, int x, int val){
if(l == r) return createleaf(val);
int m = (l+r)>>1;
if(x <= m) return createvertex(upd(L[id], l, m, x, val), R[id]);
return createvertex(L[id], upd(R[id], m+1, r, x, val));
}
int get(int id, int l, int r, int x, int y){
if(r < x or y < l) return 0;
if(x <= l and r <= y) return value[id];
int m = (l+r)>>1;
return get(L[id], l, m, x, y) + get(R[id], m+1, r, x, y);
}
int main(){
cin >> n >> k;
f(i,1,n+1) {
cin >> a[i] >> b[i];
s.insert(a[i]), s.insert(b[i]);
}
f(i,1,k+1) {
cin >> t[i];
s.insert(t[i]);
}
int ID = 0;
for(int x: s) m[x] = ++ID;
f(i,1,k+1) {
t[i] = m[t[i]];
adj[t[i]].push_back(i);
}
f(i,1,k+1) id[t[i]] = max(id[t[i]], i);
f(i,1,ID+1) st[i][0] = id[i];
f(r,1,20){
f(i,1,ID+1){
int x = i + (1<<(r-1));
if(x > ID) break;
st[i][r] = max(st[i][r-1], st[x][r-1]);
}
}
root[ID+1] = build(0, k);
fa(i,ID,0){
root[i] = root[i+1];
for(int x: adj[i]) root[i] = upd(root[i], 0, k, x, 1);
}
ll ans = 0;
f(i,1,n+1){
int x = m[a[i]], y = m[b[i]];
if(a[i] == b[i]){
ans += (ll) a[i];
continue;
}
x = min(x, y), y = max(x, y);
int iq = maxi(x, y-1), s;
s = get(root[y], 0, k, iq+1, k);
if(iq == 0){
if(s&1) ans += (ll) b[i];
else ans += (ll) a[i];
}
else{
if(s&1) ans += (ll) min(a[i], b[i]);
else ans += (ll) max(a[i], b[i]);
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
14828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
