#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
map<int,int> m;
vector<int> zh,aq[MAXN];
int a[2][MAXN],t[MAXN],seg[12*MAXN],bit[3*MAXN+7],lf[MAXN],uk;
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) {uk++; for(int i=ind;i<=3*MAXN;i+=(i&-i)) bit[i]++;}
int fval(int ind)
{
int sol=0;
for(int i=ind;i>0;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(0,sz,m[t[i]],i,1);
for(int i=0;i<n;i++) lf[i]=nmax(0,sz,m[min(a[0][i],a[1][i])],m[max(a[0][i],a[1][i])]-1,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(uk-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(uk-fval(m[c])%2==0) sol+=b;
else sol+=c;
}
printf("%lld",sol);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:39: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:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<aq[i].size();j++)
~^~~~~~~~~~~~~
fortune_telling2.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<aq[0].size();j++)
~^~~~~~~~~~~~~
fortune_telling2.cpp:34: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:35: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:36: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 |
7 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
7268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
667 ms |
20244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
