Submission #1106510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106510		Noname_1900	Nile (IOI24_nile)	C++17	51 / 100	75 ms	20260 KiB

nile

#include "nile.h"
using namespace std;
#include<bits/stdc++.h>
const int NMAX = 100000;
#define int long long
const int INFINI = 1000000000000ll;
struct T {
  int poid, normal, enPair;
  T(int prem = 0, int a = 0, int b = 0)
  {
    poid = prem;
    normal = a;
    enPair = b;
  }
  bool operator<(const T &other) const {
    return poid < other.poid;
  }
};
vector<pair<int, pair<int, int>>> aretes;
int boss[NMAX];

int minRouge[NMAX], minNoir[NMAX];
T infos[NMAX];//W, A, B
int sommeB[NMAX];
int sommeTotal;
int taille[NMAX];
int sommeComposante[NMAX];

int findBoss(int noeud)
{
  if(boss[noeud] == noeud)
  {
    return noeud;
  }
  return boss[noeud] = findBoss(boss[noeud]);
}
void comparerBalance(int noeud)
{
      minRouge[findBoss(noeud)] = min(minRouge[findBoss(noeud)], (infos[noeud].normal-infos[noeud].enPair));
      minNoir[findBoss(noeud)] = min(minNoir[findBoss(noeud)], (infos[noeud].normal-infos[noeud].enPair));
    
}
void faire(int bossA, int bossB, bool inverserCouleur)
{
  if(inverserCouleur)
  {
    minRouge[bossA] = min(minRouge[bossA], minNoir[bossB]);
    minNoir[bossA] = min(minNoir[bossA], minRouge[bossB]);
  }
  else
  {
    minRouge[bossA] = min(minRouge[bossA], minRouge[bossB]);
    minNoir[bossA] = min(minNoir[bossA], minNoir[bossB]);
  }
}
void merge(int a, int b)
{
  int bossA = findBoss(a), bossB = findBoss(b);
  if(bossA == bossB)
  {
      int balance = a+1;
      comparerBalance(balance);
      sommeTotal -= sommeComposante[bossA];
  }
  else
  {
      int debutB = bossB%2;
      int debutA = bossA%2;
      int finA = (debutA + taille[bossA]-1)%2;
      if(finA == debutB)
        faire(bossA, bossB, 1);
      else
      {
        faire(bossA, bossB, 0);
      }
      sommeB[bossA] += sommeB[bossB];
      taille[bossA] += taille[bossB];
      sommeTotal -= sommeComposante[bossA] + sommeComposante[bossB];
      boss[bossB] = bossA;
  }
  int noeud = bossA;
  if(taille[noeud]%2 == 0)
  {
    sommeComposante[noeud] = sommeB[noeud];
  }
  else if(bossA%2 == 0)
  {
    sommeComposante[noeud] = sommeB[noeud]+minRouge[noeud];
  }
  else
  {
    sommeComposante[noeud] = sommeB[noeud]+minNoir[noeud];
  }
  sommeTotal += sommeComposante[noeud];
}
pair<int, int> requetes[NMAX];
#undef int

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  #define int long long
  sommeTotal = 0;
  int Q = (int)E.size();
  int N = W.size();
  for(int i = 0; i < Q; i++)
  {
    requetes[i] = {E[i], i};
  }
  sort(requetes, requetes+Q);
  for(int i = 0; i < N; i++)
  {
    infos[i] = {W[i], A[i], B[i]};
  }
  sort(infos, infos+N);

  for(int i = 1; i < N; i++)
  {
    aretes.push_back({infos[i].poid-infos[i-1].poid, pair<int, int>(i-1, i)});
    if(i >= 2)
      aretes.push_back({infos[i].poid-infos[i-2].poid, pair<int, int>(i-2, i)});
  }
  sort(aretes.begin(), aretes.end());
  //aVoir
  for(int i = 0; i < N; i++)
  {
    boss[i] = i;
    taille[i] = 1;
    sommeTotal += infos[i].normal;
    sommeB[i] = infos[i].enPair;
    sommeComposante[i] = infos[i].normal;
    if(i % 2 == 0)
    {
      minRouge[i] = (infos[i].normal - infos[i].enPair);
      minNoir[i] = INFINI;

      
    }
    else
    {
      minNoir[i] = (infos[i].normal- infos[i].enPair);
      minRouge[i] = INFINI;

    }
    
  }
  std::vector<long long> R(Q);
  int iEnlever = 0;
  for(int i = 0; i < Q; i++)
  {
    int D = requetes[i].first;
    while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
    {
        merge(aretes[iEnlever].second.first, aretes[iEnlever].second.second);
        iEnlever++;
    }
    R[requetes[i].second] = sommeTotal;
  }
  return R;
}
/** */

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:151:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
      |            ~~~~~~~~~^~~~~~~~~~~~~~~

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