제출 #1326390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326390		warrenn	나일강 (IOI24_nile)	C++20	100 / 100	78 ms	18588 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
const int maxn=1e5;

vector<array<ll,3> >isi;
vector<ll>ans;
ll n,dsu[maxn+2],mn[maxn+2][2],mn2[maxn+2][2],sum[maxn+2],sz[maxn+2];

ll fin(int a){
  if(dsu[a]==a)return a;
  return dsu[a]=fin(dsu[a]);
}

ll comp(int a){
  a=fin(a);
  if(sz[a]%2==0)return sum[a];
  return sum[a]+min(mn2[a][a%2],mn[a][a%2]);
}

ll tot;

void merg(int a,int b){
  if(b-a==2){
    tot-=comp(fin(a));
    int apa=fin(a);
    mn2[apa][a%2]=min(mn2[apa][a%2],isi[a+1][1]-isi[a+1][2]);
    // if(a==1){
    //   cout<<apa<<" "<<mn[apa][a%2]<<endl;
    // } 
    tot+=comp(apa);
    return;
  }

  a=fin(a),b=fin(b);
  if(a==b)return;
  tot-=comp(a)+comp(b);

  if(a<b)swap(a,b);
  dsu[a]=b;
  sz[b]+=sz[a];
  sum[b]+=sum[a];
  mn[b][0]=min(mn[a][0],mn[b][0]);
  mn[b][1]=min(mn[a][1],mn[b][1]);

  mn2[b][0]=min(mn2[a][0],mn2[b][0]);
  mn2[b][1]=min(mn2[a][1],mn2[b][1]);
  tot+=comp(b);
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  n=W.size();
  for(int q=0;q<n;q++){
    isi.pb({W[q],A[q],B[q]});
  }  
  sort(isi.begin(),isi.end());
  vector<pair<ll,ll> >inter,lain;

  for(int q=0;q<n;q++){
    dsu[q]=q,mn[q][0]=mn[q][1]=mn2[q][0]=mn2[q][1]=1e18;
    mn[q][q%2]=isi[q][1]-isi[q][2];
    sum[q]=isi[q][2]; sz[q]=1;
    tot+=A[q];

    if(q){
      inter.pb({isi[q][0]-isi[q-1][0],q-1});
    }
    if(q>=2){
      lain.pb({isi[q][0]-isi[q-2][0],q-2});
    }
  }
  sort(inter.rbegin(),inter.rend());
  sort(lain.rbegin(),lain.rend());

  vector<pair<ll,ll> >qu;
  for(int q=0;q<E.size();q++){
    qu.pb({E[q],q});
    ans.pb(0);
  }
  sort(qu.begin(),qu.end());

  for(auto [mx,id] : qu){
    while(inter.size() && (inter.back()).first<=mx){
      auto [_,hah]=inter.back(); inter.pop_back();
      merg(hah,hah+1);
    }
    //cout<<id<<" "<<fin(1)<<endl;
    while(lain.size() && (lain.back()).first<=mx){
      auto [_,hah]=lain.back(); lain.pop_back();
      merg(hah,hah+2);
      // if(hah==1){
      //   cout<<_<<" k "<<mn2[1][1]<<endl;
      // }
    }
    ans[id]=tot;
  }
  
  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