#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int Nmax=200010, S=(1<<20);
int N, K;
int A[Nmax], B[Nmax], C[Nmax], inv[3*Nmax];
ll ans;
int cnt;
set<int> St;
map<int, int> Mp;
class Seg {
public:
void Update(int k, int v) {Update(1, 1, S, k, v);}
int Query(int l, int r) {return Query(1, 1, S, l, r);}
private:
int Tree[2*S];
void Update(int node, int s, int e, int k, int v) {
if(s==e) {
Tree[node]=max(Tree[node], v);
return;
}
int lch=2*node, rch=lch+1, m=(s+e)/2;
if(k<=m) Update(lch, s, m, k, v);
else Update(rch, m+1, e, k, v);
Tree[node]=max(Tree[lch], Tree[rch]);
}
int Query(int node, int s, int e, int l, int r) {
if(l>e || s>r) return 0;
if(l<=s && e<=r) return Tree[node];
int lch=2*node, rch=lch+1, m=(s+e)/2;
return max(Query(lch, s, m, l, r), Query(rch, m+1, e, l, r));
}
}T;
class PST {
public:
PST() {
root[cnt++]=0;
Tree[bcnt++]={0, 0, 0};
}
void Update(int k) {
root[cnt]=Update(root[cnt-1], 1, S, k);
cnt++;
}
ll Query(int l, int r, int v) {return Query(root[l-1], root[r], 1, S, v, S);}
private:
struct Node {int l, r, v;};
Node Tree[70101010];
int bcnt, cnt, root[Nmax];
int Update(int prev, int s, int e, int k) {
int curr=bcnt++;
Tree[curr].v=Tree[prev].v+1;
if(s==e) return curr;
int m=(s+e)/2;
if(k<=m) {
Tree[curr].l=Update(Tree[prev].l, s, m, k);
Tree[curr].r=Tree[prev].r;
}
else {
Tree[curr].l=Tree[prev].l;
Tree[curr].r=Update(Tree[prev].r, m+1, e, k);
}
Tree[curr].v=Tree[Tree[curr].l].v+Tree[Tree[curr].r].v;
return curr;
}
ll Query(int lnode, int rnode, int s, int e, int l, int r) {
if(l<=s && e<=r) return Tree[rnode].v-Tree[lnode].v;
if(l>e || s>r) return 0;
int m=(s+e)/2;
return Query(Tree[lnode].l, Tree[rnode].l, s, m, l, r)
+Query(Tree[lnode].r, Tree[rnode].r, m+1, e, l, r);
}
}P;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>K;
for(int i=1; i<=N; i++) {
cin>>A[i]>>B[i];
St.insert(A[i]); St.insert(B[i]);
}
for(int i=1; i<=K; i++) {
cin>>C[i];
St.insert(C[i]);
}
for(int i:St) Mp[i]=++cnt, inv[cnt]=Mp[i];
for(int i=1; i<=K; i++) {
T.Update(Mp[C[i]], i);
P.Update(Mp[C[i]]);
}
for(int i=1; i<=N; i++) {
int m=Mp[min(A[i], B[i])], M=Mp[max(A[i], B[i])];
int e=T.Query(m, M-1), k=P.Query(e+1, K, M);
if(!e) m=B[i], M=A[i];
if(k%2) ans+=inv[m];
else ans+=inv[M];
}
cout<<ans;
return 0;
}
Compilation message
fortune_telling2.cpp: In constructor 'PST::PST()':
fortune_telling2.cpp:38:14: warning: '*<unknown>.PST::cnt' is used uninitialized in this function [-Wuninitialized]
38 | root[cnt++]=0;
| ^~~
fortune_telling2.cpp:39:14: warning: '*<unknown>.PST::bcnt' is used uninitialized in this function [-Wuninitialized]
39 | Tree[bcnt++]={0, 0, 0};
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
