#include<iostream>
#include<map>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
struct wi{
int x,y;
}*w;
map<int,int> mapka;
int drzewo[1000000],drzewo2[1000000];
int zap[1000000];
int pot=1;
vector<pair<int,int> > Q,Q2;
int zapp(int x,int y)
{
x+=pot;
y+=pot;
int wynik=0;
wynik=drzewo[x];
wynik=max(wynik,drzewo[y]);
while(x/2!=y/2)
{
if(x%2==0)
wynik=max(wynik,drzewo[x+1]);
if(y%2==1)
wynik=max(wynik,drzewo[y-1]);
x/=2;
y/=2;
}
return wynik;
}
void dodaj(int x)
{
x+=pot;
drzewo2[x]=1;
x/=2;
while(x>=1)
{
drzewo2[x]=drzewo2[x*2]+drzewo2[x*2+1];
x/=2;
}
}
int zapp2(int x,int y)
{
x+=pot;
y+=pot;
int wynik=0;
wynik=drzewo2[x];
if(x!=y)
wynik+=drzewo2[y];
while(x/2!=y/2)
{
if(x%2==0)
wynik+=drzewo2[x+1];
if(y%2==1)
wynik+=drzewo2[y-1];
x/=2;
y/=2;
}
return wynik;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k,x,y;
cin>>n>>k;
w=new wi[n+3];
while(pot<=max(n,k))
pot*=2;
pot--;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
w[i].x=x;
w[i].y=y;
mapka[x]=1;
mapka[y]=1;
Q.push_back({max(x,y),i});
}
sort(Q.begin(),Q.end());
for(int i=1;i<=k;i++)
{
cin>>x;
mapka[x]=1;
zap[i]=x;
Q2.push_back({x,i});
}
sort(Q2.begin(),Q2.end());
int kiedy=1;
for(auto it=mapka.begin();it!=mapka.end();it++)
{
mapka[it->first]=kiedy;
kiedy++;
}
for(int i=1;i<=k;i++)
{
auto it=mapka.find(zap[i]);
drzewo[it->second+pot]=i;
}
for(int i=pot;i>=1;i--)
drzewo[i]=max(drzewo[i*2+1],drzewo[i*2]);
int wskaz=Q2.size()-1;
long long wypisz=0;
for(int i=Q.size()-1;i>=0;i--)
{
int maxx=Q[i].first;
int co=Q[i].second;
int gosciu=zapp(mapka[min(w[co].x,w[co].y)],mapka[max(w[co].x,w[co].y)]-1);
//cout<<maxx<<" "<<co<<" "<<gosciu<<" ";
while(wskaz>=0 && Q2[wskaz].first>=maxx)
{
dodaj(Q2[wskaz].second);
wskaz--;
}
int ile=zapp2(gosciu+1,pot+1);
//cout<<ile<<"\n";
if(gosciu==0)
{
if(ile%2==0)
wypisz+=w[co].x;
else wypisz+=w[co].y;
continue;
}
if(ile%2==0)
wypisz+=maxx;
else{
if(w[co].x==maxx)
wypisz+=w[co].y;
else wypisz+=w[co].x;
}
//cout<<wypisz<<"\n";
}
cout<<wypisz;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
