Language: C++

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

template <class T>
struct DelaySegmentTree{
  using F = function<T(T,T)>;
  F f;
  T inf;
  int n;
  vector<int> node,delay_val,delay_add;
  vector<bool> delayflag;

  DelaySegmentTree(vector<T> v,T inf,F f):inf(inf),f(f){
    n = 1; while(n < v.size()) n *= 2;
    node.resize(2*n-1,inf);
    delay_val.resize(2*n-1,inf);
    delay_add.resize(2*n-1,0);
    delayflag.resize(2*n-1,false);
    for(int i = 0; i < v.size(); i++) node[i+n-1] = v[i];
    for(int i = n-2; i >= 0; i--) node[i] = f(node[2*i+1],node[2*i+2]);
  }

  void eval(int k,int l,int r){
    if(delayflag[k]){
      node[k] = delay_val[k];
      if(r-l > 1){
        delay_val[2*k+1] = delay_val[2*k+2] = delay_val[k];
        delayflag[2*k+1] = delayflag[2*k+2] = true;
      }
      delayflag[k] = false;
    }
    if(delay_add[k] != 0){
      node[k] += delay_add[k];
      if(r-l > 1){
        delay_add[2*k+1] += delay_add[k] / 2;
        delay_add[2*k+2] += delay_add[k] / 2;
      }
      delay_add[k] = 0;
    }
  }

  void update(int a,int b,T x){ update(a,b,x,0,0,n); }
  void update(int a,int b,T x,int k,int l,int r){
    eval(k,l,r);
    if(b <= l || r <= a) return;
    if(a <= l && r <= b){
      delay_val[k] = x;
      delayflag[k] = true;
      eval(k,l,r);
    }
    else {
      update(a,b,x,2*k+1,l,(l+r)/2);
      update(a,b,x,2*k+2,(l+r)/2,r);
      node[k] = f(node[2*k+1],node[2*k+2]);
    }
  }

  void add(int a,int b,T x){ add(a,b,x,0,0,n); }
  void add(int a,int b,T x,int k,int l,int r){
    eval(k,l,r);
    if(b <= l || r <= a) return;
    if(a <= l && r <= b){
      delay_add[k] += x * (r - l);
      eval(k,l,r);
    }
    else {
      add(a,b,x,2*k+1,l,(l+r)/2);
      add(a,b,x,2*k+2,(l+r)/2,r);
      node[k] = f(node[2*k+1],node[2*k+2]);
    }
  }

  T getval(int a,int b){ return getval(a,b,0,0,n); }
  T getval(int a,int b,int k,int l,int r){
    //区間[a, b)の値を返す
    eval(k,l,r);
    if(b <= l || r <= a) return inf;
    if(a <= l && r <= b) return node[k];
    T vl = getval(a, b, 2*k+1, l, (l+r)/2);
    T vr = getval(a, b, 2*k+2, (l+r)/2, r);
    return f(vl, vr);
  }
};

signed main(){

  int n; cin >> n;
  vector<pair<int,int>> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i].first;
    a[i].second = i;
  }

  using P = pair<int,int>;
  const P INF = {1LL<<60,1LL<<60};
  DelaySegmentTree<P> seg(a,INF,[&](P x,P y){
    return max(x, y);
  });

  int ans = 0;
  while(1){
    auto p = seg.getval(0, n);
    int val = p.first;
    if(val < n) break;
    ans += val / n;
    seg.update(p.second, p.second+1, {val - val/n * n, i});
    seg.add(0, p.second, val / n); //pairのaddどうすんの
    seg.add(p.second+1, n, val / n);
  }
  cout << ans << endl;

  return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:110:56: error: 'i' was not declared in this scope
  110 |     seg.update(p.second, p.second+1, {val - val/n * n, i});
      |                                                        ^
a.cc:110:15: error: no matching function for call to 'DelaySegmentTree<std::pair<long long int, long long int> >::update(long long int&, long long int, <brace-enclosed initializer list>)'
  110 |     seg.update(p.second, p.second+1, {val - val/n * n, i});
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:46:8: note: candidate: 'void DelaySegmentTree<T>::update(long long int, long long int, T) [with T = std::pair<long long int, long long int>]'
   46 |   void update(int a,int b,T x){ update(a,b,x,0,0,n); }
      |        ^~~~~~
a.cc:46:29: note:   no known conversion for argument 3 from '<brace-enclosed initializer list>' to 'std::pair<long long int, long long int>'
   46 |   void update(int a,int b,T x){ update(a,b,x,0,0,n); }
      |                           ~~^
a.cc:47:8: note: candidate: 'void DelaySegmentTree<T>::update(long long int, long long int, T, long long int, long long int, long long int) [with T = std::pair<long long int, long long int>]'
   47 |   void update(int a,int b,T x,int k,int l,int r){
      |        ^~~~~~
a.cc:47:8: note:   candidate expects 6 arguments, 3 provided
a.cc:111:12: error: no matching function for call to 'DelaySegmentTree<std::pair<long long int, long long int> >::add(int, long long int&, long long int)'
  111 |     seg.add(0, p.second, val / n); //pairのaddどうすんの
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
a.cc:62:8: note: candidate: 'void DelaySegmentTree<T>::add(long long int, long long int, T) [with T = std::pair<long long int, long long int>]'
   62 |   void add(int a,int b,T x){ add(a,b,x,0,0,n); }
      |        ^~~
a.cc:62:26: note:   no known conversion for argument 3 from 'long long int' to 'std::pair<long long int, long long int>'
   62 |   void add(int a,int b,T x){ add(a,b,x,0,0,n); }
      |                        ~~^
a.cc:63:8: note: candidate: 'void DelaySegmentTree<T>::add(long long int, long long int, T, long long int, long long int, long long int) [with T = std::pair<long long int, long long int>]'
   63 |   void add(int a,int b,T x,int k,int l,int r){
      |        ^~~
a.cc:63:8: note:   candidate expects 6 arguments, 3 provided
a.cc:112:12: error: no matching function for call to 'DelaySegmentTree<std::pair<long long int, long long int> >::add(long long int, long long int&, long long int)'
  112 |     seg.add(p.second+1, n, val / n);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
a.cc:62:8: note: candidate: 'void DelaySegmentTree<T>::add(long long int, long long int, T) [with T = std::pair<long long int, long long int>]'
   62 |   void add(int a,int b,T x){ add(a,b,x,0,0,n); }
      |        ^~~
a.cc:62:26: note:   no known conversion for argument 3 from 'long long int' to 'std::pair<long long int, long long int>'
   62 |   void add(int a,int b,T x){ add(a,b,x,0,0,n); }
      |                        ~~^
a.cc:63:8: note: candidate: 'void DelaySegmentTree<T>::add(long long int, long long int, T, long long int, long long int, long long int) [with T = std::pair<long long int, long long int>]'
   63 |   void add(int a,int b,T x,int k,int l,int r){
      |        ^~~
a.cc:63:8: note:   candidate expects 6 arguments, 3 provided
a.cc: In instantiation of 'DelaySegmentTree<T>::DelaySegmentTree(std::vector<_Tp>, T, F) [with T = std::pair<long long int, long long int>; F = std::function<std::pair<long long int, long long int>(std::pair<long long int, long long int>, std::pair<long long int, long long int>)>]':
a.cc:102:4:   required from here
  102 |   });
      |    ^
a.cc:19:16: error: no matching function for call to 'std::vector<long long int>::resize(long long int, std::pair<long long int, long long int>&)'
   19 |     node.resize(2*n-1,inf);
      |     ~~~~~~~~~~~^~~~~~~~~~~
In file included from /usr/include/c++/14/vector:66,
                 from /usr/include/c++/14/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_vector.h:1013:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(size_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; size_type = long unsigned int]'
 1013 |       resize(size_type __new_size)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:1013:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_vector.h:1034:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(size_type, const value_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; size_type = long unsigned int; value_type = long long int]'
 1034 |       resize(size_type __new_size, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:1034:54: note:   no known conversion for argument 2 from 'std::pair<long long int, long long int>' to 'const std::vector<long long int>::value_type&' {aka 'const long long int&'}
 1034 |       resize(size_type __new_size, const value_type& __x)
      |                                    ~~~~~~~~~~~~~~~~~~^~~
a.cc:20:21: error: no matching function for call to 'std::vector<long long int>::resize(long long int, std::pair<long long int, long long int>&)'
   20 |     delay_val.resize(2*n-1,inf);
      |     ~~~~~~~~~~~~~~~~^~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:1013:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(size_type) [with _Tp = long long int; _Alloc = std::allocator<long long int>; size_type = long unsigned int]'
 1013 |       resize(size_type __new_size)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:1013:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_vector.h:1034:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(size_type, const value_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; size_type = long unsigned int; value_type = long long int]'
 1034 |       resize(size_type __new_size, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/14/bits/stl_vector.h:1034:54: note:   no known conversion for argument 2 from 'std::pair<long long int, long long int>' to 'const std::vector<long long int>::value_type&' {aka 'const long long int&'}
 1034 |       resize(size_type __new_size, const value_type& __x)
      |                                    ~~~~~~~~~~~~~~~~~~^~~
a.cc:23:51: error: cannot convert '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} to '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} in assignment
   23 |     for(int i = 0; i < v.size(); i++) node[i+n-1] = v[i];
a.cc:24:46: error: no match for call to '(DelaySegmentTree<std::pair<long long int, long long int> >::F {aka std::function<std::pair<long long int, long long int>(std::pair<long long int, long long int>, std::pair<long long int, long long int>)>}) (__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
   24 |     for(int i = n-2; i >= 0; i--) node[i] = f(node[2*i+1],node[2*i+2]);
      |                                             ~^~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/functional:59:
/usr/include/c++/14/bits/std_function.h:587:7: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = std::pair<long long int, long long int>; _ArgTypes = {std::pair<long long int, long long int>, std::pair<long long int, long long int>}]'
  587 |       operator()(_ArgTypes... __args) const
      |       ^~~~~~~~
/usr/include/c++/14/bits/std_function.h:587:27: note:   no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'std::pair<long long int, long long int>'
  587 |       operator()(_ArgTypes... __args) const
      |                  ~~~~~~~~~^~~~~~~~~~
a.cc: In instantiation of 'T DelaySegmentTree<T>::getval(long long int, long long int, long long int, long long int, long long int) [with T = std::pair<long long int, long long int>]':
a.cc:77:39:   required from 'T DelaySegmentTree<T>::getval(long long int, long long int) [with T = std::pair<long long int, long long int>]'
   77 |   T getval(int a,int b){ return getval(a,b,0,0,n); }
      |                                 ~~~~~~^~~~~~~~~~~
a.cc:106:24:   required from here
  106 |     auto p = seg.getval(0, n);
      |              ~~~~~~~~~~^~~~~~
a.cc:82:39: error: could not convert '((DelaySegmentTree<std::pair<long long int, long long int> >*)this)->DelaySegmentTree<std::pair<long long int, long long int> >::node.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)k))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'std::pair<long long int, long long int>'
   82 |     if(a <= l && r <= b) return node[k];
      |                                       ^
      |                                       |
      |                                       __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type {aka long long int}