Submission #1241689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241689		acoatoitgs	Nile (IOI24_nile)	C++20	38 / 100	216 ms	83060 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<ll> 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);

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

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

  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)
  {
    // cout << "Query " << q << "\n";
    while(!removals.empty())
    {
    // cout << "Removing " << removals.size() << "\n";

      auto [len, delta, idx] = removals.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)
    {
      //merge shit
      ll lg = fp(merges.back().second);
      ll rg = fp(merges.back().second+1);

      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())
      {
        //left is bigger
        P[rg] = lg;
        //merge sets
        for(auto e : gr[rg].usable) gr[lg].usable.insert(e);
        
        //remove invalid
        if(gr[lg].r != gr[lg].l && V[gr[rg].l].first-V[gr[lg].r-1].first > D)
        {
          gr[lg].usable.erase(
            gr[lg].usable.find(
              {A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r}));
        }
        if(gr[rg].r != gr[rg].l && V[gr[rg].l+1].first-V[gr[lg].r].first > D)
        {
          gr[lg].usable.erase(
            gr[lg].usable.find(
              {A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l}));
        }

        gr[lg].r = max(gr[lg].r, gr[rg].r);      
        gr[lg].l = min(gr[lg].l, gr[rg].l);

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

        gr[rg].r = max(gr[lg].r, gr[rg].r);      
        gr[rg].l = min(gr[lg].l, gr[rg].l);

        if((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