| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1187130 | ardasher_2o | Nile (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "nile.h"
#define int long long
#define fr first
#define sc second
#define pow powl
using namespace std;
const int MAX = 1e5+5;
const int MOD = 998244353, P = 29;
const int MIX = 1e15+7;
struct tree{
int sz=1;
vector<int> tre[2];
void full(int o){
while(sz<o){
sz*=2;
}
tre[0].assign(sz*2-1,-MIX);
tre[1].assign(sz*2-1,-MIX);
}
void add(int ps, int v, int z){
add(ps, v, z, 0, sz, 0);
}
void add(int ps, int v, int z, int lr, int rl, int x){
if(rl-lr==1){
tre[z][x]=v;
return;
}
int mid=(rl+lr)/2;
if(mid<=ps){
add(ps, v, z, mid, rl, x*2+2);
}
else{
add(ps, v, z, lr, mid, x*2+1);
}
tre[z][x]=max(tre[z][x*2+1],tre[z][x*2+2]);
}
int take(int L, int R, int z){
return take(L, R, z, 0, sz-1, 0);
}
int take(int L, int R, int z, int lr, int rl, int x){
if(L>rl || lr>R){
return -MIX;
}
if(L<=lr && rl<=R){
return tre[z][x];
}
int mid=(rl+lr)/2;
return max(take(L, R, z, mid+(rl+lr)%2, rl, x*2+2), take(L, R, z, lr, mid, x*2+1));
}
};
vector<int> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
tree tr;
int q = E.size();
int n = W.size(),sum=0;
tr.full(n);
for(auto i : A){
sum+=i;
}
vector<pair<int,int>> ans;
vector<int> R(q, 0),ms;
vector<pair<int,int>> vec;
for(int i=0;i<n;i++){
vec.push_back({W[i],B[i]-A[i]});
if(i==0){
ms.push_back(vec[i].sc);
}
else{
ms.push_back(ms.back()+vec[i].sc);
}
}
sort(vec.begin(),vec.end());
vector<pair<int,pair<int,int>>> color;
vector<int> price(n,0);
for(int i=0;i<n;i++) color.push_back({i,{i,i}});
set<pair<int,pair<int,int>>> dif;
for(int i=1;i<n;i++){
dif.insert({vec[i].fr-vec[i-1].fr,{i-1,1}});
}
for(int i=1;i<n-1;i++){
dif.insert({vec[i+1].fr-vec[i-1].fr,{i,2}});
}
for(int i=0;i<n;i+=2){
tr.add(i, vec[i].sc, 0);
}
for(int i=1;i<n;i+=2){
tr.add(i, vec[i].sc, 1);
}
ans.push_back({-1,sum});
while(!dif.empty()){
pair<int,pair<int,int>> pr=*dif.begin();
dif.erase(dif.begin());
if(pr.sc.sc==1){
int clr1 = color[pr.sc.fr].fr, clr2 = color[pr.sc.fr + 1].fr;
if(color[clr1].sc.sc-color[clr1].sc.fr>color[clr2].sc.sc-color[clr2].sc.fr){
color[clr1].sc.sc=color[clr2].sc.sc;
for(int i=color[clr2].sc.fr;i<=color[clr2].sc.sc;i++){
color[i].fr=clr1;
}
sum-=price[clr1]+price[clr2];
if(color[clr1].sc.fr==0){
price[clr1]=ms[color[clr1].sc.sc]-tr.take(color[clr1].sc.fr,color[clr1].sc.sc,color[clr1].sc.fr%2);
}
else{
price[clr1]=ms[color[clr1].sc.sc]-ms[color[clr1].sc.fr-1]-tr.take(color[clr1].sc.fr,color[clr1].sc.sc,color[clr1].sc.fr%2);
}
sum+=price[clr1];
}
else{
color[clr2].sc.fr=color[clr1].sc.fr;
for(int i=color[clr1].sc.fr;i<=color[clr1].sc.sc;i++){
color[i].fr=clr2;
}
sum-=price[clr1]+price[clr2];
if(color[clr2].sc.fr==0){
price[clr2]=ms[color[clr2].sc.sc]-tr.take(color[clr2].sc.fr,color[clr2].sc.sc,color[clr2].sc.fr%2);
}
else{
price[clr2]=ms[color[clr2].sc.sc]-ms[color[clr2].sc.fr-1]-tr.take(color[clr2].sc.fr,color[clr2].sc.sc,color[clr2].sc.fr%2);
}
sum+=price[clr2];
}
}
else{
tr.add(vec[pr.sc.fr].sc, pr.sc.fr, (pr.sc.fr+1)%2);
int clr = color[pr.sc.fr].fr;
sum-=price[clr];
if(color[clr].sc.fr==0){
price[clr]=ms[color[clr].sc.sc]-tr.take(color[clr].sc.fr,color[clr].sc.sc,color[clr].sc.fr%2);
}
else{
price[clr]=ms[color[clr].sc.sc]-ms[color[clr].sc.fr-1]-tr.take(color[clr].sc.fr,color[clr].sc.sc,color[clr].sc.fr%2);
}
sum+=price[clr];
}
if(ans.back().fr==pr.fr){
ans.pop_back();
}
ans.push_back({pr.fr,sum});
}
for(int i=0;i<q;i++){
int lr=0,rl=n+1;
while(rl-lr!=1){
int mid=(rl+lr)/2;
if(ans[mid].fr<=E[i]){
lr=mid;
}
else{
rl=mid;
}
}
R[i]=ans[lr].sc;
}
return R;
}