제출 #1167353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167353		epicci23	Safety (NOI18_safety)	C++20	100 / 100	628 ms	25428 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) return 0;
  if(rt -> rc) return Max(rt -> rc);
  return rt -> val;
}

int Min(Node* rt){
  recalc(rt);
  if(!rt) return 0;
  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;
    if(i > 1){
     auto X = split_by_size(T, i - 1);
     int l = Max(X[0]), r = Min(X[1]);

     if(val < l) ans += l - val;
     else if(val > r) ans += val - r;
     T = merge(X[0], X[1]);
    }
    T = Insert(T, val);
    T = Insert(T, val);
    auto X = split_by_size(T, i);
    X[0] -> lazy -= k;
    X[1] -> lazy += k;
    T = merge(X[0], X[1]);
  }

  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: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29