Submission #1241770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241770		acoatoitgs	Nile (IOI24_nile)	C++20	38 / 100	256 ms	96324 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll,ll>;

#define all(x) (x).begin(),(x).end()

vector<int> W, A, B, E;
vector<ll> P, R;
vector<pi> queries, V, merges;
int N, Q;
ll ans = 0;
priority_queue<tuple<ll,ll,ll>, vector<tuple<ll,ll,ll>>, greater<tuple<ll,ll,ll>>> removals;

struct group
{
  ll l, r;
  bool in_use;
  multiset<pi> usable;

  group() {}

  void init(ll idx)
  {
    l = r = idx;
    in_use = 1;

    usable.insert({A[V[r].second] - B[V[r].second], l});

    if(l != 0 && r != N-1)
    {
      removals.push({V[r+1].first - V[r-1].first, A[V[r].second] - B[V[r].second], l});
    }
  } 
};
vector<group> gr;

ll fp(ll pos)
{
  return (P[pos] == pos ? pos : P[pos] = fp(P[pos]));
}

vector<long long> calculate_costs(vector<int> w, vector<int> a, 
  vector<int> b, vector<int> e) {
  W = w;
  A = a;
  B = b;
  E = e;
  N = W.size();
  Q = E.size();

  R.resize(Q, 0);
  P.resize(N);
  gr.resize(N);
  
  iota(all(P), 0);

  queries.clear();
  for(ll q = 0; q < Q; q++) queries.emplace_back(E[q], q);
  V.clear();
  for(ll i = 0; i < N; i++) V.emplace_back(W[i], i), ans += A[i];

  sort(all(V));
  sort(all(queries));

  while (!removals.empty()) removals.pop();
  merges.clear();

  for(ll i = 0; i < N; i++) gr[i].init(i);
  for(ll i = 0; i < N-1; i++) merges.emplace_back(V[i+1].first - V[i].first, i);
  
  sort(all(merges), greater<pi>());

  for(auto [D, q] : queries)
  {
    while(!removals.empty())
    {
      auto top = removals.top();
      ll len = get<0>(top);
      ll delta = get<1>(top);
      ll idx = get<2>(top);
      if (len > D) break;
      removals.pop();
      ll p = fp(idx);
    
      if(gr[p].in_use)
      {
        ans -= (*gr[p].usable.begin()).first;
      }

      gr[p].usable.insert({delta, idx});

      if(gr[p].in_use)
      {
        ans += (*gr[p].usable.begin()).first;
      }
    }

    while(!merges.empty() && merges.back().first <= D)
    {
      ll idx_merge = merges.back().second;
      ll lg = fp(idx_merge);
      ll rg = fp(idx_merge+1);

      if (lg == rg) {
          merges.pop_back();
          continue;
      }

      if(gr[lg].in_use)
      {
        ans -= (*gr[lg].usable.begin()).first;
        gr[lg].in_use = 0;
      }  
      if(gr[rg].in_use)
      {
        ans -= (*gr[rg].usable.begin()).first;
        gr[rg].in_use = 0;
      } 

      if(gr[lg].usable.size() > gr[rg].usable.size())
      {
        P[rg] = lg;
        for(auto e : gr[rg].usable) gr[lg].usable.insert(e);
        
        if(gr[lg].r != gr[lg].l) 
        {
            if (V[gr[lg].r].first - V[gr[lg].r-1].first > D)
            {
                auto it = gr[lg].usable.find({A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r});
                if (it != gr[lg].usable.end()) {
                    gr[lg].usable.erase(it);
                }
            }
        }
        if(gr[rg].r != gr[rg].l) 
        {
            if (V[gr[rg].l+1].first - V[gr[rg].l].first > D)
            {
                auto it = gr[lg].usable.find({A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l});
                if (it != gr[lg].usable.end()) {
                    gr[lg].usable.erase(it);
                }
            }
        }

        gr[lg].r = gr[rg].r;      

        if(gr[lg].r - gr[lg].l + 1 > 1 && (gr[lg].r - gr[lg].l) % 2 == 0) 
        {
            ans += (*gr[lg].usable.begin()).first;
            gr[lg].in_use = 1;
        }
      }
      else
      {
        P[lg] = rg;
        for(auto e : gr[lg].usable) gr[rg].usable.insert(e);
        
        if(gr[lg].r != gr[lg].l) 
        {
            if (V[gr[lg].r].first - V[gr[lg].r-1].first > D)
            {
                auto it = gr[rg].usable.find({A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r});
                if (it != gr[rg].usable.end()) {
                    gr[rg].usable.erase(it);
                }
            }
        }
        if(gr[rg].r != gr[rg].l) 
        {
            if (V[gr[rg].l+1].first - V[gr[rg].l].first > D)
            {
                auto it = gr[rg].usable.find({A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l});
                if (it != gr[rg].usable.end()) {
                    gr[rg].usable.erase(it);
                }
            }
        }

        gr[rg].l = gr[lg].l;      

        if(gr[rg].r - gr[rg].l + 1 > 1 && (gr[rg].r - gr[rg].l) % 2 == 0) 
        {
            ans += (*gr[rg].usable.begin()).first;
            gr[rg].in_use = 1;
        }

      }
      merges.pop_back();
    }
    R[q] = ans;
  }
  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