Submission #1242076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242076		mychecksedad	Nile (IOI24_nile)	C++20	100 / 100	145 ms	21944 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define cerr if(0) cerr
#define all(x) x.begin(),x.end()
#define ll long long int
const int N = 1e5+100;

int _n;
ll T[N*2], T2[2*N];
void build(int n){
  _n = n;
  for(int j = 0; j <= 2*n+2; ++j) T[j] = T2[j] = 1e18;
}
void upd(int p, ll val){
  ++p;
  if(p&1){
    T[p += _n] = val;
    for(p >>= 1; p; p >>= 1) T[p] = min(T[p<<1], T[p<<1|1]);
  }else{
    T2[p += _n] = val;
    for(p >>= 1; p; p >>= 1) T2[p] = min(T2[p<<1], T2[p<<1|1]);
  }
}
void upd2(int p, ll val){
  ++p;
  if(!(p&1)){
    T[p += _n] = val;
    for(p >>= 1; p; p >>= 1) T[p] = min(T[p<<1], T[p<<1|1]);
  }else{
    T2[p += _n] = val;
    for(p >>= 1; p; p >>= 1) T2[p] = min(T2[p<<1], T2[p<<1|1]);
  }
}
ll get(int l, int r){
  if(l > r) return 1e18;
  ll res = 1e18;
  ++l, ++r;
  if(l&1){
    l += _n;
    r += _n + 1;
    for(; l < r; l >>= 1, r >>= 1){
      if(l&1) res = min(res, T[l++]);
      if(r&1) res = min(res, T[--r]);
    }  
  }else{
    l += _n;
    r += _n + 1;
    for(; l < r; l >>= 1, r >>= 1){
      if(l&1) res = min(res, T2[l++]);
      if(r&1) res = min(res, T2[--r]);
    }
  }
  return res;
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  int q = (int) E.size();
  int n = (int) W.size();
  build(n);
  vector<array<ll, 3>> C;
  for(int i = 0; i < n; ++i) C.pb({W[i], A[i], B[i]});
  sort(all(C)); 
  
  vector<ll> pref(n);
  ll sum = 0;
  for(int i = 0; i < n; ++i) sum += C[i][1];
  pref[0] = C[0][1] - C[0][2];
  for(int i = 1; i < n; ++i) pref[i] = pref[i - 1] + C[i][1] - C[i][2];


  for(int i = 0; i < n; ++i) upd(i, C[i][1] - C[i][2]);

  // for(int i = 0; i < n; ++i) cerr << pref[i] << ' ';
  // cerr << " wtf\n";

  function<ll(int, int)> get2 = [&](int l, int r){
    if(l == r) return 0ll;
    if((r-l) % 2){
      return pref[r] - (l <= 0 ? 0 : pref[l - 1]);
    }
    ll summ = pref[r] - (l <= 0 ? 0 : pref[l - 1]);
    return summ - get(l, r);
  };

  vector<ll> res(q);
  vector<pair<ll, int>> Q;
  for(int i = 0; i < q; ++i) Q.pb({E[i], i});
  sort(all(Q));

  set<array<int, 2>> S;
  for(int i = 0; i < n; ++i) S.insert({i, i});


  vector<pair<ll, ll>> dif;
  vector<pair<ll, ll>> adj;
  for(int i = 1; i < n; ++i) dif.pb({C[i][0] - C[i - 1][0], i});
  for(int i = 1; i + 1 < n; ++i) adj.pb({C[i + 1][0] - C[i - 1][0], i});


  sort(all(dif));
  sort(all(adj));
  
  int ptr = 0;
  int ptr2 = 0;
  ll ans = 0;
  
  for(auto [D, idx]: Q){
    cerr << D << ":\n";
    while(ptr2 + 2 < n && adj[ptr2].ff <= D){
      int pt = adj[ptr2].ss;

      auto it = S.lower_bound(array<int, 2>{pt + 1, -1});
      --it;
      ans -= get2((*it)[0], (*it)[1]);

      upd2(pt, C[pt][1] - C[pt][2]);
      
      ans += get2((*it)[0], (*it)[1]);
      
      cerr << pt << ' ';
      ptr2++;
    }
    cerr << '\n';
    while(ptr + 1 < n && dif[ptr].ff <= D){
      int pt = dif[ptr].ss;
      // cerr << pt << ' ';
      auto it = S.lower_bound(array<int, 2>{pt, -1});
      ans -= get2((*it)[0], (*it)[1]);
      ans -= get2((*prev(it))[0], (*prev(it))[1]);
      int L = (*prev(it))[0];
      int R = (*it)[1];
      S.erase(prev(it));
      it = S.lower_bound(array<int, 2>{pt, -1});
      S.erase(it);
      S.insert({L, R});
      // cerr << L << ' ' << R << ' ' << get2(L, R) << " ff\n";
      ans += get2(L, R);
      ++ptr;
    }
    cerr << '\n';
    cerr << ans << '\n';
    cerr << "S:\n";
    res[idx] = sum - ans;
  }

  return res;
}

• 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