#include <bits/stdc++.h>
using namespace std;
map<int,int> m;
vector<int> zh,aq[400014];
int a[2][200007],t[200007],seg[1600056],bit[4000014],inv[200007],lf[200007];
void upd(int l,int r,int v,int val,int ind)
{
if(l==r) {seg[ind]=val; return;}
int s=(l+r)/2;
if(s>=v) upd(l,s,v,val,2*ind);
else upd(s+1,r,v,val,2*ind+1);
seg[ind]=max(seg[2*ind],seg[2*ind+1]);
}
int nmax(int l,int r,int lt,int rt,int ind)
{
if(l>r) return 0;
if(l>=lt && r<=rt) return seg[ind];
if(r<lt || l>rt) return 0;
int s=(l+r)/2;
return max(nmax(l,s,lt,rt,2*ind),nmax(s+1,r,lt,rt,2*ind+1));
}
void updf(int ind) {for(int i=ind;i<=zh.size();i+=(i&-i)) bit[i]++;}
int fval(int ind)
{
int sol=0;
for(int i=ind;i;i-=(i&-i)) sol+=bit[i];
return sol;
}
int main()
{
int n,k;
long long sol=0;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) {scanf("%d%d",&a[0][i],&a[1][i]); zh.push_back(a[0][i]); zh.push_back(a[1][i]);}
for(int i=1;i<=k;i++) {scanf("%d",&t[i]); zh.push_back(t[i]);}
sort(zh.begin(),zh.end());
int sz=zh.size();
for(int i=0;i<zh.size();i++) m[zh[i]]=i;
for(int i=1;i<=k;i++) upd(1,sz,m[t[i]],i,1);
for(int i=0;i<n;i++) lf[i]=nmax(1,sz,min(a[0][i],a[1][i]),max(a[0][i],a[1][i]),1);
for(int i=0;i<n;i++) aq[lf[i]].push_back(i);
for(int i=k;i>=1;i--)
{
updf(m[t[i]]+1);
for(int j=0;j<aq[i].size();j++)
{
int b=min(a[0][aq[i][j]],a[1][aq[i][j]]),c=max(a[0][aq[i][j]],a[1][aq[i][j]]);
if((fval(sz)-fval(m[c]))%2==0) sol+=c;
else sol+=b;
}
}
for(int j=0;j<aq[0].size();j++)
{
int b=a[0][aq[0][j]],c=a[1][aq[0][j]];
if((fval(sz)-fval(m[c]))%2==0) sol+=b;
else sol+=c;
}
printf("%lld",sol);
}
Compilation message
fortune_telling2.cpp: In function 'void updf(int)':
fortune_telling2.cpp:22:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
void updf(int ind) {for(int i=ind;i<=zh.size();i+=(i&-i)) bit[i]++;}
~^~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<zh.size();i++) m[zh[i]]=i;
~^~~~~~~~~~
fortune_telling2.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<aq[i].size();j++)
~^~~~~~~~~~~~~
fortune_telling2.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<aq[0].size();j++)
~^~~~~~~~~~~~~
fortune_telling2.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:34:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0;i<n;i++) {scanf("%d%d",&a[0][i],&a[1][i]); zh.push_back(a[0][i]); zh.push_back(a[1][i]);}
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:35:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=k;i++) {scanf("%d",&t[i]); zh.push_back(t[i]);}
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
12408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
502 ms |
27584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
