#include "nile.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int p[N];
int root(int i){
return (i==p[i]?i:p[i]=root(p[i]));
}
vector<ll> calculate_costs(vector<int>w,
vector<int>a,
vector<int>b,
vector<int>e){
int n=w.size();
int q=e.size();
sort(w.begin(),w.end());
map<int,vector<int>>ord;
for(int i=0;i<q;i++){
ord[e[i]].push_back(i);
}
sort(e.begin(),e.end());
int sz[n];
vector<pair<int,int>>g;
for(int i=0;i<n;i++){
p[i]=i;
if(i){
g.push_back({w[i]-w[i-1],i-1});
}
sz[i]=1;
}
sort(g.begin(),g.end());
vector<ll>res(q);
ll cost=2*n;
int i=0;
for(int d:e){
if(ord[d].empty()){
continue;
}
while(i<n-1){
auto[x,l]=g[i];
if(x>d){
break;
}
int r=l+1;
l=root(l);
r=root(r);
if(sz[l]%2&&sz[r]%2){
cost-=2;
}
sz[l]+=sz[r];
p[r]=l;
i++;
}
for(int j:ord[d]){
res[j]=cost;
}
ord[d].clear();
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |