Submission #1214484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214484		hyakup	Nile (IOI24_nile)	C++20	13 / 100	93 ms	22464 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using tripla = tuple<ll, ll, ll>;

const ll inf = 1e18;

struct Evento{
  ll prior, a, b; Evento( ll prior, ll a, ll b ) : prior(prior), a(a), b(b) {}
  bool operator < ( Evento e ){
    if( prior != e.prior ) return prior < e.prior;
    if( a != e.a ) return a < e.a;
    return b < e.b;
  }
}; vector<Evento> line;


vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e ){
  int n = w.size();
  int q = e.size();

  vector<tripla> v;

  ll tot = 0;
  vector<ll> total(n), pai(n), pares(n, inf), impares(n), livres(n, inf), tam(n, 1);
  iota( pai.begin(), pai.end(), 0 );

  map<ll, int> cont;
  cont[-inf] = 1;
  cont[inf] = 1;

  for( int i = 0; i < n; i++ ){
    v.emplace_back( w[i], a[i], b[i] );
    tot += a[i];
    cont[w[i]]++;
  }

  sort( v.begin(), v.end() );


  for( int i = 0; i < n; i++ ){
    auto [w1, a1, b1] = v[i];
    if( cont[w1] >= 3 ) line.push_back( Evento( 0, -1, i ) );
    else if( cont[w1] == 2 ){
      ll dist = inf;
      for( int j = max( 0, i - 3 ); j < min( n - 1, i + 3); j++ ) if( get<0>(v[j]) != w1 ) dist = min( dist, (ll)abs(w1 - get<0>(v[j])));

      line.push_back( Evento( dist, -1, i ) );
    }
    if( i + 1 < n ){
      auto [w2, a2, b2] = v[i + 1];
      line.push_back( Evento( w2 - w1, i, i + 1 ) );
      if( i > 0 ){
        auto [w3, a3, b3] = v[i - 1];
        line.push_back( Evento( w2 - w3, n, i ) );
      }
    }
    total[i] = a1 - b1;
    impares[i] = a1 - b1;
  }


  for( int i = 0; i < q; i++ ){
    line.push_back( Evento( e[i], n + 1, i ) );
  }

  sort( line.begin(), line.end() );

  vector<ll> resp(q);

  auto get_total = [&]( int id ){
    if( tam[id]%2 == 0 ) return 0LL;
    return min( livres[id], impares[id] );
  };

  function<int(int)> find = [&]( int a ){
    return (( pai[a] == a ) ? a : pai[a] = find(pai[a]));
  };

  auto join = [&]( int a, int b ){
     a = find(a); b = find(b);
     if( a == b ) return;
     tot -= (total[a] + total[b]);
     if( tam[a]%2 == 1 ){
       impares[a] = min( impares[a], pares[b] );
       pares[a] = min( pares[a], impares[b] );
     }
     else{
       impares[a] = min( impares[a], impares[b] );
       pares[a] = min( pares[a], pares[b] );
     }
     livres[a] = min( livres[a], livres[b] );
     tam[a] += tam[b];
     total[a] = get_total(a);
     tot += total[a];
     pai[b] = a;
  };


  for( auto cur : line ){
    if( cur.a == n + 1 ) resp[cur.b] = tot;
    else if( cur.a == n ){
      auto [w1, a1, b1] = v[cur.b];
      int id = find(cur.b);
      livres[id] = min( livres[id], a1 - b1 );

      tot -= total[id];
      total[id] = get_total(id);
      tot += total[id];
    }
    else join( cur.a, cur.b );
  }
  return resp;
}

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