#include <bits/stdc++.h>
using namespace std;
int n,k,sz;
int a[200005];
int b[200005];
int t[200005];
int bit[200005];
int comp[600005];
pair<int,int> pos[200005];
vector<int> v[800005];
void insrt(int start,int val,int i,int j,int l,int r)
{
if(i==l && j==r)
{
v[start].push_back(val);
return;
}
int m=(l+r)/2;
if(i<m)insrt(2*start+1,val,i,min(j,m),l,m);
if(j>m)insrt(2*start+2,val,max(i,m),j,m,r);
}
void check(int start,int j,int tt,int l,int r)
{
for(int i=0;i<v[start].size();i++)
{
if(v[start][i]<0)
{
v[start][i]=j;
}
}
v[start].clear();
if(r-l==1)return;
int m=(l+r)/2;
if(tt<m)check(2*start+1,j,tt,l,m);
else
{
check(2*start+2,j,tt,m,r);
}
}
void update(int x)
{
while(x<=sz)
{
bit[x]++;
x+=x&(-x);
}
}
int sum(int x)
{
int rez=0;
while(x>0)
{
rez+=bit[x];
x-=x&(-x);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
int ind=0;
for(int i=0;i<n;i++)
{
cin >> a[i] >> b[i];
comp[ind++]=a[i];
comp[ind++]=b[i];
}
for(int i=0;i<k;i++)
{
cin >> t[i];
comp[ind++]=t[i];
}
sort(comp,comp+ind);
sz=unique(comp,comp+ind)-comp;
for(int i=0;i<n;i++)
{
a[i]=lower_bound(comp,comp+sz,a[i])-comp;
b[i]=lower_bound(comp,comp+sz,b[i])-comp;
pos[i]=make_pair(-1,i);
insrt(0,i,min(a[i],b[i]),max(a[i],b[i]),0,sz);
}
for(int i=k-1;i>=0;i--)
{
t[i]=lower_bound(comp,comp+sz,t[i])-comp;
check(0,i,t[i],0,sz);
}
sort(pos,pos+n);
reverse(pos,pos+n);
int cur=k-1;
int br=0;
long long rez=0;
for(int i=0;i<n;i++)
{
while(cur>pos[i].first)
{
update(t[cur--]+1);
br++;
}
int p=pos[i].second;
int num=(br-sum(max(b[p],a[p])))%2;
int beg=1;
if(cur<0)beg=0;
int fin;
if((num+beg)%2)
{
fin=max(a[p],b[p]);
}
else
{
fin=min(a[p],b[p]);
}
rez+=comp[fin];
}
cout << rez;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'void check(int, int, int, int, int)':
fortune_telling2.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<v[start].size();i++)
| ~^~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int sum(int)':
fortune_telling2.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
57 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3036 ms |
19200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3036 ms |
19200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3036 ms |
19200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
