oj.uz

Submission #1113887

# Submission time Handle Problem Language Result Execution time Memory
1113887 2024-11-17T17:35:46 Z Andrei_Calota Nile (IOI24_nile) C++17
13 / 100
 63 ms 15556 KB 
#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 - e1.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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 15556 KB Output is correct
2 Correct 52 ms 15552 KB Output is correct
3 Correct 51 ms 15540 KB Output is correct
4 Correct 58 ms 15556 KB Output is correct
5 Correct 55 ms 15540 KB Output is correct
6 Correct 48 ms 15536 KB Output is correct

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 15548 KB Output is correct
2 Correct 54 ms 15536 KB Output is correct
3 Correct 63 ms 15540 KB Output is correct
4 Correct 63 ms 15540 KB Output is correct
5 Incorrect 62 ms 15540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 15548 KB Output is correct
2 Correct 54 ms 15536 KB Output is correct
3 Correct 63 ms 15540 KB Output is correct
4 Correct 63 ms 15540 KB Output is correct
5 Incorrect 62 ms 15540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 2 ms 592 KB Output isn't correct
3 Halted 0 ms 0 KB -