Submission #1113888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113888		Andrei_Calota	Nile (IOI24_nile)	C++17	100 / 100	95 ms	21428 KiB

nile

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

using namespace std;
using int64 = long long;


const int N_MAX = 1e5;
const int Q_MAX = 1e5;
const int64 myINF = 1e18;

int64 answer;
struct DSU {
    int father;
    int le, ri;
    int64 min_d[2], min_jump[2];
    int64 local_answer;
} infos[1 + N_MAX];

struct elem {
   int64 w;
   int64 s, p;
   int64 diff;
}; vector<elem> input;
bool byW (elem first, elem second) {return first.w < second.w;}

int __find (int a) {
   if (infos[a].father == a) return a;
   return infos[a].father = __find (infos[a].father);
}
void __merge (int a, int b) {
   int x = __find (a), y = __find (b);

   infos[y].father = x;
   if (b == a + 1) {
      answer -= infos[x].local_answer;
      answer -= infos[y].local_answer;

      infos[x].ri = infos[y].ri;
      for (int t = 0; t < 2; t ++) {
         infos[x].min_d[t] = min (infos[x].min_d[t], infos[y].min_d[t]);
         infos[x].min_jump[t] = min (infos[x].min_jump[t], infos[y].min_jump[t]);
      }
   }
   else {
     answer -= infos[x].local_answer;
     infos[x].min_jump[(a + 1) % 2] = min (infos[x].min_jump[(a + 1) % 2], input[a + 1].diff);
   }
   int l = infos[x].le, r = infos[x].ri;
   if ((r - l + 1) % 2 == 0)
      infos[x].local_answer = 0;
   else
      infos[x].local_answer = min (infos[x].min_d[l % 2], infos[x].min_jump[1 - l % 2]);
   answer += infos[x].local_answer;
}

struct defEdge {
    int a, b;
    int64 cost;
};
bool compare_edges (defEdge e1, defEdge e2) {
   if (e1.cost == e2.cost) return (e1.b - e1.a < e2.b - e2.a);
   return e1.cost < e2.cost;
}


vector<int64> calculate_costs (vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  int N = W.size ();
  int Q = E.size ();

  input.resize (N);
  for (int i = 0; i < N; i ++) input[i] = {W[i], A[i], B[i], A[i] - B[i]};

  int64 sumB = 0;
  for (int i = 0; i < N; i ++) {
     answer += input[i].diff;
     sumB += input[i].p;
  }

  vector<pair<int, int>> querys (Q);
  vector<int64> R(Q, 0);
  for (int i = 0; i < Q; i ++) querys[i] = make_pair (E[i], i);


  sort (input.begin (), input.end (), byW);
  vector<defEdge> edges;
  for (int i = 0; i < N; i ++) {
     if (i < N - 1) edges.push_back ({i, i + 1, input[i + 1].w - input[i].w});
     if (i < N - 2) edges.push_back ({i, i + 2, input[i + 2].w - input[i].w});
  }
  sort (edges.begin (), edges.end (), compare_edges);

  for (int i = 0; i < N; i ++) {
     infos[i].father = i;
     infos[i].le = i, infos[i].ri = i;
     infos[i].min_d[i % 2] = input[i].diff;
     infos[i].min_jump[i % 2] = myINF;
     infos[i].min_d[1 - i % 2] = infos[i].min_jump[1 - i % 2] = myINF;
     infos[i].local_answer = input[i].diff;
  }

  sort (querys.begin (), querys.end ());
  int e = 0;
  for (int i = 0; i < Q; i ++) {
     while (e < (int)edges.size () && edges[e].cost <= querys[i].first) {
        __merge (edges[e].a, edges[e].b);
        ///cout << edges[e].a << " " <<  edges[e].b << endl;
        e ++;
     }
     R[querys[i].second] = sumB + answer;
  }
  return R;
}

/**int main () {
    vector<int64> R = calculate_costs({2, 10, 12, 15, 21}, {5, 6, 4, 5, 3}, {2, 3, 2, 1, 2}, {1, 5, 9});
    for (int r : R) cout << r << " ";
}**/

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