Submission #1205154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205154		HappyCapybara	Nile (IOI24_nile)	C++20	100 / 100	383 ms	87656 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int N, cd;
vector<ll> d;
vector<int> W;
vector<vector<vector<ll>>> st;

void merge(int node, int tl, int tr){
  int tm = (tl+tr)/2;
  for (int i=0; i<3; i++){
    for (int j=0; j<3; j++) st[node][i][j] = max(st[node][i][j], st[node*2][i][0]+st[node*2+1][0][j]);
  }
  if (W[tm+1]-W[tm] <= cd){
    for (int i=0; i<3; i++){
      for (int j=0; j<3; j++) st[node][i][j] = max(st[node][i][j], d[tm]+d[tm+1]+st[node*2][i][1]+st[node*2+1][1][j]);
    }
  }
  if (tm+2 <= tr && W[tm+2]-W[tm] <= cd){
    for (int i=0; i<3; i++){
      for (int j=0; j<3; j++) st[node][i][j] = max(st[node][i][j], d[tm]+d[tm+2]+st[node*2][i][1]+st[node*2+1][2][j]);
    }
  }
  if (tm-1 >= tl && W[tm+1]-W[tm-1] <= cd){
    for (int i=0; i<3; i++){
      for (int j=0; j<3; j++) st[node][i][j] = max(st[node][i][j], d[tm-1]+d[tm+1]+st[node*2][i][2]+st[node*2+1][1][j]);
    }
  }
  for (int i=0; i<3; i++){
    for (int j=0; j<3; j++){
      if (i+j > tr-tl+1) st[node][i][j] = -pow(10, 18);
      else st[node][i][j] = max(st[node][i][j], 0ll);
    }
  }
}

void update(int pos, int node=1, int tl=0, int tr=N-1){
  if (tl == tr) return;
  int tm = (tl+tr)/2;
  if (pos <= tm) update(pos, node*2, tl, tm);
  else update(pos, node*2+1, tm+1, tr);
  merge(node, tl, tr);
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
  N = W.size();
  ::W = W;
  int Q = E.size();
  d.resize(N);
  for (int i=0; i<N; i++) d[i] = i;
  sort(d.begin(), d.end(), [](int a, int b){return ::W[a] < ::W[b];});
  for (int i=0; i<N; i++) d[i] = A[d[i]]-B[d[i]];
  st.resize(4*N, {{0ll, 0ll, (ll)-pow(10, 18)}, {0ll, (ll)-pow(10, 18), (ll)-pow(10, 18)}, {(ll)-pow(10, 18), (ll)-pow(10, 18), (ll)-pow(10, 18)}});
  vector<pair<int,int>> ev;
  sort(W.begin(), W.end());
  ::W = W;
  for (int i=0; i<N-1; i++) ev.push_back({W[i+1]-W[i], i});
  for (int i=0; i<N-2; i++) ev.push_back({W[i+2]-W[i], i});
  sort(ev.begin(), ev.end());
  vector<pair<int,ll>> res = {{0, 0}};
  for (auto [nd, i] : ev){
    cd = nd;
    update(i);
    if (!res.empty() && res.back().first == nd) res.back().second = st[1][0][0];
    else res.push_back({nd, st[1][0][0]});
  }
  ll t = 0;
  for (int i=0; i<N; i++) t += A[i];
  vector<ll> ans(Q);
  for (int i=0; i<Q; i++){
    int l = 0, r = res.size();
    while (l < r-1){
      int m = (l+r)/2;
      if (res[m].first <= E[i]) l = m;
      else r = m;
    }
    ans[i] = t-res[l].second;
  }
  return ans;
}

• 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