#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+3;
const int inf=1e15+7;
int a[maxn], b[maxn], t[maxn], last[maxn], seg[4*maxn], qm[maxn];
map<int,int>relaciona, disrelaciona;
void update(int id, int ini, int fim, int cara, int val){
if(ini==fim){
seg[id]=val;
return;
}
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
if(cara<=mid) update(e,ini,mid,cara,val);
else update(d,mid+1,fim,cara,val);
seg[id]=max(seg[e],seg[d]);
}
int query(int id, int ini, int fim, int l, int r){
if(ini>r||fim<l) return 0;
if(l<=ini&&fim<=r) return seg[id];
int mid=(ini+fim)/2, e=2*id, d=2*id+1;
return max(query(e,ini,mid,l,r),query(d,mid+1,fim,l,r));
}
int bit[3*maxn];
void add(int id){
for(int i=id;i<3*maxn;i+=(i&-i)) bit[i]++;
}
int sum(int id){
int ret=0;
for(int i=id;i>0;i-=(i&-i)) ret+=bit[i];
return ret;
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, k; cin >> n >> k;
set<int>comp;
for(int i=1;i<=n;i++){
cin >> a[i] >> b[i]; comp.insert(a[i]); comp.insert(b[i]);
}
set<pair<int,int>>process;
for(int i=1;i<=k;i++){
cin >> t[i]; comp.insert(t[i]);
}
int cnt=0;
for(int x : comp){
cnt++;
relaciona[x]=cnt;
disrelaciona[cnt]=x; // para ter a soma original de volta qnd imprimir
}
// comprimindo as coordenadas
for(int i=1;i<=n;i++) a[i]=relaciona[a[i]];
for(int i=1;i<=n;i++) b[i]=relaciona[b[i]];
for(int i=1;i<=k;i++) t[i]=relaciona[t[i]];
// agr tds os caras são a[i],b[i],t[j]<=600.000=2*N+K, qtd de caras distintos
for(int i=1;i<=k;i++) process.insert({t[i],i});
int id=0;
for(pair<int,int> p : process){ // passando por t[j] crescente, e colocando na seg o indice do cara
id++;
update(1,1,k,id,p.second);
}
process.insert({inf,inf});
vector<pair<int,int>>final;
for(int i=1;i<=n;i++){
auto x=process.lower_bound({min(a[i],b[i]),0}), y=process.lower_bound({max(a[i],b[i]),0});
// x eh o primeiro valor q troca o min(a[i],b[i])
// y-1 eh o ultimo cara q troca apenas o min(a[i],b[i])
if(x->second==y->second) last[i]=0;
else{
y--;
int l=x->second, r=y->second;
last[i]=query(1,1,k,l,r);// qual foi a ultima vez, q eu teve um t[j], t.q. min(a[i],b[i])<=t[j]<max(a[i],b[i])
}
final.push_back({last[i],i});
}
sort(final.begin(),final.end());
int resp=0;
for(int i=k;i>=1;i--){
while(final.size()&&final.back().first>=i){ // já posso contar qnts caras tiveram dps da última vez q foi o maior
int id=final.back().second;
if(a[id]<b[id]) swap(a[id],b[id]);
int qtd=sum(3*maxn-1)-sum(a[id]-1);
if(qtd%2) resp+=disrelaciona[b[id]];
else resp+=disrelaciona[a[id]];
if(qtd%2) qm[id]=disrelaciona[b[id]];
else qm[id]=disrelaciona[a[id]];
final.pop_back();
//cout << resp << " " << qm[id] << endl;
}
add(t[i]);
}
while(final.size()){ // já posso contar qnts caras tiveram dps da última vez q foi o maior
// nesse caso, n existe j, t.q. min(a[i],b[i])<=t[j]<max(a[i],b[i]), ent tds as operações funcionam nos dois
int id=final.back().second;
int qtd=sum(3*maxn-1)-sum(max(a[id],b[id])-1);
if(qtd%2) resp+=disrelaciona[b[id]];
else resp+=disrelaciona[a[id]];
if(qtd%2) qm[id]=disrelaciona[b[id]];
else qm[id]=disrelaciona[a[id]];
final.pop_back();
//cout << resp << " " << qm[id] << endl;
}
//for(int i=1;i<=n;i++) cout << qm[i] << " ";
//cout << endl;
cout << resp << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |