oj.uz

Submission #1113888

# Submission time Handle Problem Language Result Execution time Memory
1113888 2024-11-17T17:36:05 Z Andrei_Calota Nile (IOI24_nile) C++17
100 / 100
 95 ms 21428 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 - 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 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Correct 3 ms 592 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15540 KB Output is correct
2 Correct 46 ms 15540 KB Output is correct
3 Correct 46 ms 15508 KB Output is correct
4 Correct 46 ms 15540 KB Output is correct
5 Correct 48 ms 15540 KB Output is correct
6 Correct 44 ms 15548 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15596 KB Output is correct
2 Correct 47 ms 15544 KB Output is correct
3 Correct 54 ms 15540 KB Output is correct
4 Correct 54 ms 15556 KB Output is correct
5 Correct 63 ms 15548 KB Output is correct
6 Correct 71 ms 17072 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 848 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 3 ms 592 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 772 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 52 ms 15540 KB Output is correct
8 Correct 46 ms 15540 KB Output is correct
9 Correct 46 ms 15508 KB Output is correct
10 Correct 46 ms 15540 KB Output is correct
11 Correct 48 ms 15540 KB Output is correct
12 Correct 44 ms 15548 KB Output is correct
13 Correct 46 ms 15596 KB Output is correct
14 Correct 47 ms 15544 KB Output is correct
15 Correct 54 ms 15540 KB Output is correct
16 Correct 54 ms 15556 KB Output is correct
17 Correct 63 ms 15548 KB Output is correct
18 Correct 71 ms 17072 KB Output is correct
19 Correct 3 ms 848 KB Output is correct
20 Correct 2 ms 848 KB Output is correct
21 Correct 3 ms 592 KB Output is correct
22 Correct 3 ms 848 KB Output is correct
23 Correct 3 ms 1016 KB Output is correct
24 Correct 3 ms 592 KB Output is correct
25 Correct 58 ms 18100 KB Output is correct
26 Correct 61 ms 18356 KB Output is correct
27 Correct 72 ms 18356 KB Output is correct
28 Correct 63 ms 18356 KB Output is correct
29 Correct 68 ms 18360 KB Output is correct
30 Correct 69 ms 18364 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15596 KB Output is correct
2 Correct 47 ms 15544 KB Output is correct
3 Correct 54 ms 15540 KB Output is correct
4 Correct 54 ms 15556 KB Output is correct
5 Correct 63 ms 15548 KB Output is correct
6 Correct 71 ms 17072 KB Output is correct
7 Correct 76 ms 19636 KB Output is correct
8 Correct 81 ms 19892 KB Output is correct
9 Correct 94 ms 19892 KB Output is correct
10 Correct 93 ms 19892 KB Output is correct
11 Correct 95 ms 19892 KB Output is correct
12 Correct 86 ms 19816 KB Output is correct
13 Correct 87 ms 19788 KB Output is correct
14 Correct 82 ms 19636 KB Output is correct
15 Correct 92 ms 19764 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 772 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 52 ms 15540 KB Output is correct
9 Correct 46 ms 15540 KB Output is correct
10 Correct 46 ms 15508 KB Output is correct
11 Correct 46 ms 15540 KB Output is correct
12 Correct 48 ms 15540 KB Output is correct
13 Correct 44 ms 15548 KB Output is correct
14 Correct 46 ms 15596 KB Output is correct
15 Correct 47 ms 15544 KB Output is correct
16 Correct 54 ms 15540 KB Output is correct
17 Correct 54 ms 15556 KB Output is correct
18 Correct 63 ms 15548 KB Output is correct
19 Correct 71 ms 17072 KB Output is correct
20 Correct 3 ms 848 KB Output is correct
21 Correct 2 ms 848 KB Output is correct
22 Correct 3 ms 592 KB Output is correct
23 Correct 3 ms 848 KB Output is correct
24 Correct 3 ms 1016 KB Output is correct
25 Correct 3 ms 592 KB Output is correct
26 Correct 58 ms 18100 KB Output is correct
27 Correct 61 ms 18356 KB Output is correct
28 Correct 72 ms 18356 KB Output is correct
29 Correct 63 ms 18356 KB Output is correct
30 Correct 68 ms 18360 KB Output is correct
31 Correct 69 ms 18364 KB Output is correct
32 Correct 76 ms 19636 KB Output is correct
33 Correct 81 ms 19892 KB Output is correct
34 Correct 94 ms 19892 KB Output is correct
35 Correct 93 ms 19892 KB Output is correct
36 Correct 95 ms 19892 KB Output is correct
37 Correct 86 ms 19816 KB Output is correct
38 Correct 87 ms 19788 KB Output is correct
39 Correct 82 ms 19636 KB Output is correct
40 Correct 92 ms 19764 KB Output is correct
41 Correct 84 ms 21184 KB Output is correct
42 Correct 87 ms 21324 KB Output is correct
43 Correct 87 ms 21292 KB Output is correct
44 Correct 92 ms 21284 KB Output is correct
45 Correct 92 ms 21424 KB Output is correct
46 Correct 86 ms 21424 KB Output is correct
47 Correct 86 ms 21428 KB Output is correct
48 Correct 78 ms 21176 KB Output is correct
49 Correct 95 ms 21428 KB Output is correct