Submission #1305302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305302		nicknamedtwice	Nile (IOI24_nile)	C++20	100 / 100	68 ms	11576 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std; using ll=long long;
static constexpr ll INF=(ll)4e18;
vector<long long> calculate_costs(
    vector<int> W, vector<int> A,
    vector<int> B, vector<int> E
){
 int N=W.size(),Q=E.size();
 vector<int>o(N); iota(o.begin(),o.end(),0);
 sort(o.begin(),o.end(),[&](int i,int j){return W[i]<W[j];});
 vector<ll>w(N),C(N); ll base=0;
 for(int i=0;i<N;i++){int id=o[i];w[i]=W[id];C[i]=(ll)A[id]-B[id];base+=B[id];}
 vector<unsigned long long>ev;
 for(int i=0;i+1<N;i++)ev.push_back((w[i+1]-w[i])<<32|i);
 for(int i=0;i+2<N;i++)ev.push_back((w[i+2]-w[i])<<32|(1ull<<31)|i);
 sort(ev.begin(),ev.end());
 vector<int>qi(Q); iota(qi.begin(),qi.end(),0);
 sort(qi.begin(),qi.end(),[&](int i,int j){return E[i]<E[j];});
 vector<int>p(N),sz(N,1); vector<ll>a(N),b(N,INF),c(N,INF);
 for(int i=0;i<N;i++)p[i]=i,a[i]=C[i];
 auto f=[&](int x){while(p[x]!=x)p[x]=p[p[x]],x=p[x];return x;};
 auto con=[&](int r){return(sz[r]&1)?min(a[r],c[r]):0ll;};
 ll extra=accumulate(C.begin(),C.end(),0ll);
 auto uni=[&](int x,int y){
  x=f(x);y=f(y);if(x==y)return;if(x>y)swap(x,y);
  extra-=con(x)+con(y); ll ne,no;
  if(sz[x]&1)ne=min(a[x],b[y]),no=min(b[x],a[y]);
  else ne=min(a[x],a[y]),no=min(b[x],b[y]);
  p[y]=x; sz[x]+=sz[y]; a[x]=ne; b[x]=no; c[x]=min(c[x],c[y]);
  extra+=con(x);
 };
 auto mid=[&](int i){
  int r=f(i); ll o=con(r); c[r]=min(c[r],C[i]); extra+=con(r)-o;
 };
 vector<ll>ans(Q); int ptr=0;
 for(int id:qi){
  while(ptr<(int)ev.size()&&(ev[ptr]>>32)<=E[id]){
   int i=ev[ptr]&0x7fffffff;
   ((ev[ptr]>>31)&1)?mid(i+1):uni(i,i+1); ptr++;
  }
  ans[id]=base+extra;
 }
 return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18