#include <bits/stdc++.h>
#define MAXN 5000007
using namespace std;
map<int,int> m;
vector<int> zh,aq[MAXN];
int a[2][MAXN],t[MAXN],seg[4*MAXN],bit[4*MAXN],lf[MAXN];
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<=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((fval(MAXN)-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(MAXN)-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 |
Runtime error |
2 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
352 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
352 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
