Submission #1167318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167318		epicci23	Safety (NOI18_safety)	C++20	0 / 100	252 ms	16660 KiB

safety

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());


struct Node{
  Node* lc;
  Node* rc;
  int pri,sub,val,lazy;
  Node(int x){
  	lc = rc = NULL;
  	sub = 1;
  	lazy = 0;
  	val = x;
  	pri = rng();
  }
};

inline int get_sub(Node *rt){
  if(!rt) return 0;
  return rt -> sub;
}

inline void recalc(Node* rt){
  if(!rt) return;
  int u = rt -> lazy;
  rt -> lazy = 0;
  rt -> val += u;
  if(rt -> lc) rt -> lc -> lazy += u;
  if(rt -> rc) rt -> rc -> lazy += u;
  rt -> sub = 1 + get_sub(rt -> lc) + get_sub(rt -> rc);
}

Node* merge(Node* a,Node* b){
  recalc(a), recalc(b);
  if(!a || !b) return (!a ? b : a);
  if(a -> pri > b -> pri){
    a -> rc = merge(a -> rc, b);
    recalc(a);
    return a;
  }
  else{
    b -> lc = merge(a, b -> lc);
    recalc(b);
    return b;
  }
}

array<Node*,2> split_by_size(Node* a,int k){
  recalc(a);
  if(!a) return {NULL, NULL};
  if(!k) return {NULL, a};
  if(get_sub(a -> lc) >= k){
    auto X = split_by_size(a -> lc, k);
    a -> lc = X[1];
    recalc(a);
    return {X[0], a};
  }
  else{
    auto X = split_by_size(a -> rc, k - get_sub(a -> lc) - 1);
    a -> rc = X[0];
    recalc(a);
    return {a, X[1]};
  }
}

array<Node*,2> split_by_key(Node* a,int k){
  recalc(a);
  if(!a) return {NULL, NULL};
  if(a -> val <= k){
    auto X = split_by_key(a -> rc, k);
    a -> rc = X[0];
    recalc(a);
    return {a, X[1]};
  }
  else{
    auto X = split_by_key(a -> lc, k);
    a -> lc = X[1];
    recalc(a);
    return {X[0], a};
  }
}

int Max(Node* rt){
  recalc(rt);
  if(rt -> rc) return Max(rt -> rc);
  return rt -> val;
}

int Min(Node* rt){
  recalc(rt);
  if(rt -> lc) return Min(rt -> lc);
  return rt -> val;
}

Node* Insert(Node* rt, int val){
  recalc(rt);
  auto X = split_by_key(rt, val);
  return merge(merge(X[0],new Node(val)),X[1]);
}

void _(){
  int n, k;
  cin >> n >> k;
  
  int ans = 0;
  Node* T = NULL;

  for(int i=1;i<=n;i++){
    int val; cin >> val;
    T = Insert(T, val);
    recalc(T);
    T = Insert(T, val);
    recalc(T);
    auto X = split_by_size(T, i);
    recalc(X[0]), recalc(X[1]);
    ans += Min(X[1]) - Max(X[0]);
    X[0] -> lazy -= k;
    X[1] -> lazy += k;
    recalc(X[0]), recalc(X[1]);
    T = merge(X[0], X[1]);
    recalc(T);
  }

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 5
• Subtask 5: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29