#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int Nm=2e5+5;
ll ans;
int n,q,L,R,S;
int l[Nm],r[Nm],t[Nm];
int G[3*Nm],Last[3*Nm],Rf[3*Nm],v[6*Nm];
pair < int , int > Id[Nm];
vector < int > s;
map < int , int > f;
void Build(Tree) {
if (l==r) { v[h]=Last[l]; return ;}
Build(Left),Build(Right);
v[h]=max(v[(h<<1)],v[((h<<1)|1)]);
}
int Get(Tree) {
if (r<L || R<l) return 0;
if (L<=l && r<=R) return v[h];
int x=Get(Left),y=Get(Right);
return max(x,y);
}
void Up(int x) {
while (x<=S) {
G[x]++;
x+=(x & -x);
}
}
int Ge(int x) {
int res=0;
while (x>0) {
res+=G[x];
x-=(x & -x);
}
return res;
}
main () {
scanf("%d%d",&n,&q);
for (int i=1; i<=n; i++) {
scanf("%d%d",&l[i],&r[i]);
s.pb(l[i]),s.pb(r[i]);
}
for (int i=1; i<=q; i++) {
scanf("%d",&t[i]);
s.pb(t[i]);
}
sort(s.begin(),s.end());
s.erase(unique(s.begin(),s.end()),s.end());
for (int i=0; i<s.size(); i++) f[s[i]]=i+1,Rf[i+1]=s[i];
for (int i=1; i<=n; i++) l[i]=f[l[i]],r[i]=f[r[i]];
for (int i=1; i<=q; i++) t[i]=f[t[i]];
S=s.size();
for (int i=1; i<=q; i++) Last[t[i]]=i;
Build(1,1,S);
for (int i=1; i<=n; i++) {
L=min(l[i],r[i]),R=max(l[i],r[i])-1;
Id[i].F=Get(1,1,S),Id[i].S=i;
}
sort(Id+1,Id+n+1);
int Q=q,tot=0;
for (int i=n; i>=1; i--) {
while (Q && Id[i].F<Q) Up(t[Q]),--Q;
tot=Ge(S)-Ge(max(l[Id[i].S],r[Id[i].S])-1);
if (Id[i].F && l[Id[i].S]<r[Id[i].S])
swap(l[Id[i].S],r[Id[i].S]);
if (tot%2)
ans+=Rf[r[Id[i].S]];
else
ans+=Rf[l[Id[i].S]];
}
printf("%I64d\n",ans);
}
Compilation message
fortune_telling2.cpp:49:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<s.size(); i++) f[s[i]]=i+1,Rf[i+1]=s[i];
~^~~~~~~~~
fortune_telling2.cpp:94:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
printf("%I64d\n",ans);
^
fortune_telling2.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&l[i],&r[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&t[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
