Submission #1191632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191632		hamzabc	Nile (IOI24_nile)	C++20	38 / 100	73 ms	10684 KiB

nile

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


using namespace std;
#define all(x) x.begin(), x.end()


int goDSU(int a, vector<int> &DSU){
  if (DSU[a] == a)
    return a;
  DSU[a] = goDSU(DSU[a], DSU);
  return DSU[a];
}


vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  int Q = (int)E.size(), N = W.size();
  vector<long long> R(Q, 0);
  vector<array<int, 3>> artifacts(N);
  vector<array<int, 2>> query(Q);
  for (int i = 0; i < N; i++){
    artifacts[i][0] = W[i];
    artifacts[i][1] = B[i];
    artifacts[i][2] = A[i] - B[i];
  }
  for (int i = 0; i < Q; i++){
    query[i][0]= E[i];
    query[i][1] = i;
  }
  sort(all(artifacts));
  sort(all(query));
  priority_queue<array<int, 2>> pque;
  vector<int> DSU(N);
  vector<int> unused(N);
  vector<int> minL(N);
  vector<int> minR(N);
  vector<int> sz(N, 1);
  vector<int> usablemin(N, INT_MAX);
  long long ret = 0;
  for (int i = 0; i < N; i++){
    DSU[i] = i;
    unused[i] = artifacts[i][2];
    minL[i] = artifacts[i][2];
    minR[i] = artifacts[i][2];
    ret += artifacts[i][1] + artifacts[i][2];
    if (i){
      pque.push({ -artifacts[i][0] + artifacts[i - 1][0], i });
      if (i != N - 1)
        pque.push({ -artifacts[i + 1][0] + artifacts[i - 1][0], -i });
    }
  }
  for (int q = 0; q < Q; q++){
    while (pque.size() && -pque.top()[0] <= query[q][0]){
      if (pque.top()[1] < 0){
        int i = pque.top()[1] * -1;
        usablemin[goDSU(i, DSU)] = min(usablemin[goDSU(i, DSU)], artifacts[i][2]);
        if (unused[goDSU(i, DSU)] && unused[goDSU(i, DSU)] > usablemin[goDSU(i, DSU)]){
          ret -= unused[goDSU(i, DSU)];
          unused[goDSU(i, DSU)] = usablemin[goDSU(i, DSU)];
          ret += unused[goDSU(i, DSU)];
        }
        pque.pop();
        continue;
      }
      if (unused[goDSU(pque.top()[1], DSU)] && unused[goDSU(pque.top()[1] - 1, DSU)]){
        ret -= unused[goDSU(pque.top()[1], DSU)] + unused[goDSU(pque.top()[1] - 1, DSU)];
        unused[goDSU(pque.top()[1] - 1, DSU)] = 0;
        unused[goDSU(pque.top()[1], DSU)] = 0;
      }else if (unused[goDSU(pque.top()[1] - 1, DSU)]){
        unused[goDSU(pque.top()[1], DSU)] = unused[goDSU(pque.top()[1] - 1, DSU)];
        unused[goDSU(pque.top()[1] - 1, DSU)] = 0;
      }
      if (sz[goDSU(pque.top()[1], DSU)] >= 4){
        usablemin[goDSU(pque.top()[1], DSU)] = min(usablemin[goDSU(pque.top()[1], DSU)], artifacts[pque.top()[1] + 1][2]);
      }
      if (sz[goDSU(pque.top()[1], DSU)] >= 3 && sz[goDSU(pque.top()[1] - 1, DSU)] >= 2){
        usablemin[goDSU(pque.top()[1], DSU)] = min(usablemin[goDSU(pque.top()[1], DSU)], artifacts[pque.top()[1]][2]);
      }
      if (sz[goDSU(pque.top()[1], DSU)] >= 2 && sz[goDSU(pque.top()[1] - 1, DSU)] >= 3){
        usablemin[goDSU(pque.top()[1], DSU)] = min(usablemin[goDSU(pque.top()[1], DSU)], artifacts[pque.top()[1] - 1][2]);
      }
      if (sz[goDSU(pque.top()[1] - 1, DSU)] >= 4){
        usablemin[goDSU(pque.top()[1], DSU)] = min(usablemin[goDSU(pque.top()[1], DSU)], artifacts[pque.top()[1] - 2][2]);
      }
      if (unused[goDSU(pque.top()[1], DSU)] && unused[goDSU(pque.top()[1], DSU)] != min(min(minL[goDSU(pque.top()[1], DSU)], minR[goDSU(pque.top()[1], DSU)]), usablemin[goDSU(pque.top()[1], DSU)])){
        ret -= unused[goDSU(pque.top()[1], DSU)];
        unused[goDSU(pque.top()[1], DSU)] = min(min(minL[goDSU(pque.top()[1], DSU)], minR[goDSU(pque.top()[1], DSU)]), usablemin[goDSU(pque.top()[1], DSU)]);
        ret += unused[goDSU(pque.top()[1], DSU)];
      }
      sz[goDSU(pque.top()[1], DSU)] += sz[goDSU(pque.top()[1] - 1, DSU)];
      DSU[goDSU(pque.top()[1] - 1, DSU)] = goDSU(pque.top()[1], DSU);
      pque.pop();
    }
    R[query[q][1]] = ret;
  }
  return R;
}

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