Submission #1135282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135282		SkillIssueWAGuy	Nile (IOI24_nile)	C++20	100 / 100	267 ms	49592 KiB

nile

#include "nile.h"
#include<vector>
#include<utility>
#include<algorithm>
#include<cmath>
#include<malloc.h>
#include<cassert>
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
using pii = pair<ll,ll>;
using vi = vector<ll>;
using vpi = vector<pair<ll,ll>>;
ll N, Q, S, s;
vi output, F, D, C, odd, even, psum;
vpi w, e, moves;
struct ptree {
  ll l, r, v, sz;
  ptree *lc, *rc;
  void construct(){
    sz = r - l + 1;
    v = 0;
    if (l == r) return;
    lc = (ptree*)(malloc(sizeof(ptree)));
    rc = (ptree*)(malloc(sizeof(ptree)));
    lc -> l = l;
    rc -> r = r;
    lc -> r = floor((l + r) / 2.0);
    rc -> l = lc -> r + 1;
    lc -> construct();
    rc -> construct();
  }
  void update(ll pos){
    if (l == r){
      v = 1;
      return;
    }
    if (pos <= lc -> r){
      lc -> update(pos);
    }
    else {
      rc -> update(pos);
    }
    if (lc -> v == lc -> sz){
      v = lc -> v + rc -> v;
    }
    else {
      v = lc -> v;
    }
  }
  ll query(ll pos){
    if (l == r){
      return pos;
    }
    if (pos <= lc -> r){
      return lc -> query(pos);
    }
    else {
      if (rc -> v < pos - rc -> l + 1){
        return rc -> query(pos);
      }
      else {
        return lc -> query(lc -> r);
      }
    }
  }
};
struct ec{
  bool operator() (pii a, pii b){
    return a.first < b.first;
  }
};
inline ll conv(ll i){
  return (ll)floor(i/2.0L);
}
struct stree {
  ll l, r, v;
  stree *lc, *rc;
  void construct(){
    this -> v = 1e9;
    if (l == r) return;
    this -> lc = (stree*)(malloc(sizeof(stree)));
    this -> rc = (stree*)(malloc(sizeof(stree)));
    lc -> l = l;
    rc -> r = r;
    lc -> r = (ll)floor((l+r)/2.0L);
    rc -> l = lc -> r + 1;
    lc -> construct();
    rc -> construct();
  }
  void update(ll pos, ll val){
    if (l == r){
      v = val;
      return;
    }
    if (pos <= lc -> r){
      lc -> update(pos, val);
    }
    else {
      rc -> update(pos, val);
    }
    v = min(lc -> v, rc -> v);
  }
  ll query(ll left, ll right){
    if (right < left){
      return 1e18;
    }
    if (left == l && right == r){
      return v;
    }
    ll out = 1e18;
    if (left <= lc -> r){
      out = min(out,lc -> query(left, min(right, lc -> r)));
    }
    if (right >= rc -> l){
      out = min(out,rc -> query(max(rc -> l, left), right));
    }
    return out;
  }
};
stree oddr, evenr, oddf, evenf;
ptree root;
bool mc(pii a, pii b){
  return w[a.second].first - w[a.first].first > w[b.second].first - w[b.first].first;
}
inline ll fc(ll i, ll choice){
  return (i-choice)/2.0;
}
ll check_range(ll l, ll r){
  ll out = psum[r+1] - psum[l];
  if (r%2 != l%2) return out;
  ll sub = 1e18;
  if (l%2 == 0){
    sub = min(evenf.query(fc(l,0), fc(r,0)), oddr.query(fc(l+1,1), fc(r-1,1)));
  }
  else {
    sub = min(evenr.query(fc(l+1,0), fc(r-1,0)), oddf.query(fc(l,1), fc(r,1)));
  }
  return out - sub;
}
void makemove(){
  pii cur = moves.back();
  moves.pop_back();
  if (cur.second - cur.first == 1){
    s -= C[D[cur.first]];
    s -= C[cur.second];
    F[D[cur.first]] = F[cur.second];
    D[F[cur.second]] = D[cur.first];
    root.update(cur.second);
    C[D[cur.first]] = check_range(D[cur.first], F[cur.second]);
    s += C[D[cur.first]];
  }
  else {
    ll p = cur.first + 1;
    if (p%2 == 0){
      evenr.update(fc(p, 0), w[p].second);
    }
    else {
      oddr.update(fc(p, 1), w[p].second);
    }
    ll pos = root.query(p);
    s -= C[pos];
    C[pos] = check_range(pos, F[pos]);
    s += C[pos];
  }
  //cerr << S - s << '\n';
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
  Q = (ll)E.size();
  N = (ll)W.size();
  S = s = 0;
  for (int i = 0; i < N; i++){
    w.push_back({W[i], A[i] - B[i]});
    S += A[i];
  }
  for (int i = 0; i < Q; i++){
    e.push_back({E[i], i});
    output.push_back(0);
  }
  sort(w.begin(), w.end(), ec());
  sort(e.begin(), e.end(), ec());
  psum.push_back(0);
  oddr.v = 0;
  oddr.l = 0;
  oddr.r = conv(N-2);
  evenr.v = 0;
  evenr.l = 0;
  evenr.r = conv(N-1);
  oddf.v = 0;
  oddf.l = 0;
  oddf.r = conv(N-2);
  evenf.v = 0;
  evenf.l = 0;
  evenf.r = conv(N-1);
  root.l = 0;
  root.r = N-1;
  root.construct();
  oddr.construct();
  oddf.construct();
  evenf.construct();
  evenr.construct();
  for (int i = 0; i < N; i++){
    if (i%2 == 1){
      oddf.update(fc(i, 1), w[i].second);
    }
    else {
      evenf.update(fc(i,0), w[i].second);
    }
    psum.push_back(psum.back() + w[i].second);
    F.push_back(i);
    D.push_back(i);
    C.push_back(0);
  }
  
  for (int i = 0; i < N-2; i++){
    moves.push_back({i, i+2});
  }
  for (int i = 0; i < N-1; i++){
    moves.push_back({i, i+1});
  }
  sort(moves.begin(), moves.end(), mc);
  for (int i = 0; i < Q; i++){
    while (moves.size() > 0){
      if (w[moves.back().second].first - w[moves.back().first].first > e[i].first){
        break;
      }
      makemove();
    }
    output[e[i].second] = S - s;
  }
  return output;
}

• 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