Submission #1254817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254817		zzzzzzzzzzzzzzz	Nile (IOI24_nile)	C++20	38 / 100	125 ms	32192 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll MAXN=1<<18;
const ll INF=1e18;
ll parent[MAXN], rli[MAXN];
vector<ll> seg1(2*MAXN,INF), seg2(2*MAXN,INF);
vector<pair<ll,ll>> E2, sli;
vector<pair<ll,ll>> l, l2; // l은 답 저장용, l2는 구간 차이 저장용 
vector<ll> ansli(MAXN), ansli2(MAXN), ansli3(MAXN), ansli4(MAXN, 1), ansli5(MAXN); 
// 각 구간에서 시작하는 답 저장하기. ansli:구간합, ansli2:구간 짝수 인덱스 최소, ansli3: 구간 홀수 인덱스 최소
// ansli4: 짝수 구간인가 홀수 구간인가?

ll findp(ll a){
  if(a==parent[a]) return a;
  return parent[a]=findp(parent[a]);
}

void uni(ll a, ll b){
  ll a2=findp(a);
  ll b2=findp(b);
  if(a2==b2) return;
  if(a2>b2) swap(a2,b2);
  parent[b2]=a2;
  rli[a2]=max(rli[b2],rli[a2]);
}

ll query(ll node, ll s, ll e, ll l, ll r){
  if(e<l || s>r) return INF;
  if(l<=s || e<=r){
    if(l%2==0) return seg1[node];
    else return seg2[node];
  }
  ll mid=(s+e)>>1;
  return min(query(2*node,s,mid,l,r),query(2*node+1,mid+1,e,l,r));
}

void update(ll node, ll s, ll e, ll idx, ll x){
  if(idx<s || idx>e) return;
  if(s==e){
    if(idx%2==0) seg1[node]=x;
    else seg2[node]=x;
    return;
  }
  ll mid=(s+e)>>1;
  update(2*node,s,mid,idx,x);
  update(2*node+1,mid+1,e,idx,x);
  seg1[node]=min(seg1[node*2],seg1[node*2+1]);
  seg2[node]=min(seg2[node*2],seg2[node*2+1]);
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  ll N = (int)W.size();
  ll Q = (int)E.size();
  for(ll i=0;i<N;i++) rli[i]=parent[i]=i;
  ll ans=0;
  for(ll i=0;i<N;i++) ans+=A[i];
  for(ll i=0;i<N;i++) {
    l.push_back({W[i],A[i]-B[i]});
  }
  sort(l.begin(),l.end());
  for(ll i=0;i<N;i++){
    ansli[i]=ansli2[i]=l[i].second;
    ansli3[i]=INF;
    if(i>0 && i<N-1){
      sli.push_back({l[i+1].first-l[i-1].first,i});
    }
  }
  for(ll i=0;i<N-1;i++) l2.push_back({l[i+1].first-l[i].first,i});
  sort(l2.begin(),l2.end());
  vector<ll> R(Q, 0);
  for(ll i=0;i<Q;i++) E2.push_back({E[i],i});
  sort(E2.begin(),E2.end());
  sort(sli.begin(),sli.end());
  ll ne=0;
  ll j=0;
  ll k=0;
  for(ll i=0;i<Q;i++){
    while(k<N-2 && sli[k].first<=E2[i].first){
      update(1,0,MAXN-1,sli[k].second,l[sli[k].second].second);
      k++;
    }
    while(j<N-1 && l2[j].first<=E2[i].first){
      ll p1=findp(l2[j].second), p2=findp(l2[j].second+1);
      ans+=ansli5[p1];
      ans+=ansli5[p2];
      uni(l2[j].second,l2[j].second+1); // 병합할 때 끝 인덱스도 같이 관리해야 한다.
      ll p3=findp(l2[j].second);
      ll l=p3, r=rli[p3];
      if(ansli4[p1]==0){//앞에가 짝수였다면
        ansli2[p3]=min(ansli2[p1],ansli2[p2]);
        ansli3[p3]=min(ansli3[p1],ansli3[p2]);
      } 
      else{
        ansli2[p3]=min(ansli2[p1],ansli3[p2]);
        ansli3[p3]=min(ansli3[p1],ansli2[p2]);
      }
      ansli[p3]=ansli[p1]+ansli[p2];
      if((r-l)%2==1) ansli4[p3]=0;
      else ansli4[p3]=1;
      ansli5[p3]=ansli[p3]-min(ansli2[p3],query(1,0,MAXN-1,l+1,r-1))*ansli4[p3];
      ans-=ansli5[p3];
      j+=1;
    }
    R[E2[i].second]=ans;
    ne=E2[i].first;
  }
  return R;
}

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