| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1231716 | Muhammad_Aneeq | Nile (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include "nile.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int const N=1e5+10;
struct node
{
long long od=1e9+10,ev=1e9+10,sz=0;
};
long long par[N],sz[N],vl[N],l[N],r[N],n;
long long sm=0;
node dmy;
node comb(node a,node b)
{
node c;
c.sz=a.sz+b.sz;
if (a.sz%2)
{
c.od=min(a.od,b.ev);
c.ev=min(a.ev,b.od);
}
else
{
c.od=min(a.od,b.od);
c.ev=min(a.ev,b.ev);
}
return c;
}
struct ST
{
node seg[4*N]={};
node get(int l,int r,int i=1,int st=0,int en=n-1)
{
if (st>=l&&en<=r)
return seg[i];
if (st>r||en<l)
return dmy;
int mid=(st+en)/2;
return comb(get(l,r,i*2,st,mid),get(l,r,i*2+1,mid+1,en));
}
void update(int r,long long val,int i=1,int st=0,int en=n-1)
{
if (st==en)
{
seg[i].sz=1;
seg[i].od=val;
return;
}
int mid=(st+en)/2;
if (r<=mid)
update(r,val,i*2,st,mid);
else
update(r,val,i*2+1,mid+1,en);
seg[i]=comb(seg[i*2],seg[i*2+1]);
}
};
int root(int n)
{
return (par[n]==n?n:par[n]=root(par[n]));
}
ST sg1,sg2;
void upd(int u)
{
u=root(u);
if (sz[u]%2)
{
sm-=vl[u];
node z=sg1.get(l[u],r[u]);
node y=sg2.get(l[u],r[u]);
long long ad=min(z.od,y.ev);
sm+=ad;
vl[u]=ad;
}
}
void merge(int u,int v)
{
u=root(u),v=root(v);
if (u==v) return;
sm-=vl[u];
sm-=vl[v];
sz[u]+=sz[v];
par[v]=u;
l[u]=min(l[u],l[v]);
r[u]=max(r[u],r[v]);
vl[u]=0;
vl[v]=0;
upd(u);
}
vector<long long> calculate_costs(vector<int> w, vector<int> a,vector<int> b, vector<int>Q)
{
vector<vector<int>>g;
n=w.size();
for (int i=0;i<n;i++)
{
g.push_back ({w[i],a[i],b[i]});
par[i]=l[i]=r[i]=i;
sz[i]=1;
vl[i]=0;
}
sort(begin(g),end(g));
for (int i=0;i<n;i++)
{
w[i]=g[i][0],a[i]=g[i][1],b[i]=g[i][2];
vl[i]=a[i]-b[i];
sg1.update(i,a[i]-b[i]);
sm+=a[i];
}
for (int i=0;i<n;i++)
sg2.update(i,1e9+10);
// for (int j=0;j<3;j++)
// {
// for (int i=0;i<n;i++)
// cout<<g[i][j]<<' ';
// cout<<endl;
// }
int q=Q.size();
vector<long long>ans(q,0);
vector<pair<int,int>>qu;
for (int i=0;i<q;i++)
qu.push_back({Q[i],i});
sort(begin(qu),end(qu));
vector<pair<int,int>>fi,se;
for (int i=0;i+1<n;i++)
{
fi.push_back({w[i+1]-w[i],i});
if (i)
se.push_back({w[i+1]-w[i-1],i});
}
sort(begin(se),end(se));
sort(begin(fi),end(fi));
reverse(begin(se),end(se));
reverse(begin(fi),end(fi));
for (int i=0;i<q;i++)
{
int el=qu[i].first;
while (fi.size()&&el>=fi.back().first)
{
int ind=fi.back().second;
fi.pop_back();
merge(ind,ind+1);
}
while (se.size()&&el>=se.back().first)
{
int ind=se.back().second;
se.pop_back();
sg2.update(ind,a[ind]-b[ind]);
upd(ind);
}
ans[qu[i].second]=sm;
}
return ans;
}