Submission #66574207

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifdef INCLUDED_MAIN
int solve(){
    l2(n,l);
    vector<ll> p(n);
    rep(i,n-1){l1(d); p[i+1]=(p[i]+d)%l;}
    if(l%3) return cout<<0,0;
    ll t=l/3,ans=0;
    unordered_map<ll,vector<int>> m;
    m.reserve(n*1.3);
    rep(i,n) m[p[i]].push_back(i);
    for(auto&[_,v]:m) ssort(v);
    rep(i,n){
        auto &v1=m[(p[i]+t)%l], &v2=m[(p[i]+2*t)%l];
        auto u=upper_bound(all(v1),i), w=upper_bound(all(v2),i);
        ans+=(v1.end()-u)*(v2.end()-w);
    }
    cout<<ans;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifdef INCLUDED_MAIN

int solve(){
    l2(n,l);
    vector<ll> p(n);
    rep(i,n-1){l1(d); p[i+1]=(p[i]+d)%l;}
    if(l%3) return cout<<0,0;
    ll t=l/3,ans=0;
    unordered_map<ll,vector<int>> m;
    m.reserve(n*1.3);
    rep(i,n) m[p[i]].push_back(i);
    for(auto&[_,v]:m) ssort(v);
    rep(i,n){
        auto &v1=m[(p[i]+t)%l], &v2=m[(p[i]+2*t)%l];
        auto u=upper_bound(all(v1),i), w=upper_bound(all(v2),i);
        ans+=(v1.end()-u)*(v2.end()-w);
    }
    cout<<ans;
    return 0;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

#else


/*
============================================================================
                         Template for Atcoder
============================================================================

thank you.
https://ei1333.github.io/library/


*** You are FREE to use this code. ****
*** However, use at YOUR OWN RISK. ****



#ifdef INCLUDED_MAIN

int main()
{
    // main function, solve function
}

#else

    // Template code
    // .........

#define INCLUDED_MAIN
#include FILE

#endif


'''
By writting it this way, I include my self(the template) and place it below
main function.
However, please note that this currently only works on AtCoder
-it may not work on platforms like Codeforces.
'''

*/

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <numeric>
#include <limits>
#include <iterator>
#include <cassert>
#include <stack>
#include <queue>
#include <deque>
#include <random>
#include <sstream>
#include <chrono>
#include <stdexcept>
#include <set>
#include <map>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

/*****************  Macros  *************************************************/
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(n) for (int i = 0; i < (n); ++i)
#define rep3(i, a, b) for (int i = a; i <= (b); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rrep1(n) for(int i = (n)-1; i >= 0; i--)
#define rrep3(i,a,b) for(int i = (b)-1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ssort(v) sort(all(v))
#define lsort(v) sort(all(v), greater<>())
#define pb push_back
#define eb emplace_back
#define str string
#define cp(a) cout << (a) << endl
#define yes(cond) cout << ((cond) ? "Yes" : "No") << endl
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define l1(var) ll var; cin >> var
#define l2(a,b) ll a,b; cin >> a >> b
#define l3(a,b,c) ll a,b,c; cin >> a >> b >> c
#define l4(a,b,c,d) ll a,b,c,d; cin >> a >> b >> c >> d
#define l5(a,b,c,d,e) ll a,b,c,d,e; cin >> a >> b >> c >> d >> e
#define st1(var) string var; cin >> var
#define st2(a,b) string a,b; cin >> a >> b
#define st3(a,b,c) string a,b,c; cin >> a >> b >> c
#define st4(a,b,c,d) string a,b,c,d; cin >> a >> b >> c >> d
#define st5(a,b,c,d,e) string a,b,c,d,e; cin >> a >> b >> c >> d >> e
#define lary(a, x) vector<long long> a(x); for (int i = 0; i < (x); ++i) cin >> a[i];
#define iary(a, x) vector<int> a(x); for (int i = 0; i < (x); ++i) cin >> a[i];
#define sary(a, x) vector<string> a(x); for (int i = 0; i < (x); ++i) cin >> a[i];
#define l2ary(a, r, c) vector<vector<ll>> a(r, vector<ll>(c)); \
                         for (int i=0; i<(r); ++i) for (int j=0; j<(c); ++j) cin >> a[i][j];
#define i2ary(a, r, c) vector<vector<int>> a(r, vector<int>(c)); \
                         for (int i=0; i<(r); ++i) for (int j=0; j<(c); ++j) cin >> a[i][j];

template<class T> bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;}
template<class T> bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;}



/*****************  i128  *************************************************/
// using i128 = _int128;
// constexpr i128 to_integer(const string&s) {
//     i128 = 0;
//     for (auto c:s) {
//         if (isdigit(c)) res=res * 10 + ( c - '0');
//     }
//     if (s[0] == '-') res*= -1;
//     return res;
// }
// istream& operator >> (istream &is, i128 &x) {
//     string s;
//     is >> s;
//     x = to_integer(s);
//     return is;
// }
// ostream& operator << (ostream &os, const i128 &x) {
//     int 128 ax = (x >= 0 ? x : -x);
//     char buffer[128];
//     char *d = end(buffer);
//     do {
//         --d;
//         *d = "0123456789"[ax % 10];
//         ax /= 10;
//     } while (ax != 0);
//     if( x < = 0) {
//         --d;
//         *d = '-';
//     }
//     int len = end(buffer) - d;
//     if (os.rdbuf() -> sputn(d, len) != len) {
//         os.setstate(ios_base::badbint);
//     }
//     return os;
// }

// graph
template <typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}

  operator int() const { return to; }
};

template <typename T = int>
struct Graph {
  vector<vector<Edge<T> > > g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }

  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) cin >> c;
      if (directed)
        add_directed_edge(a, b, c);
      else
        add_edge(a, b, c);
    }
  }

  inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }

  inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};

template <typename T = int>
using Edges = vector<Edge<T> >;
// seg

template <typename S2, typename Op, typename E>
struct LambdaMonoid {
  using S = S2;
  S op(const S &a, const S &b) const { return _op(a, b); }

  S e() const { return _e(); }

  LambdaMonoid(Op _op, E _e) : _op(_op), _e(_e) {}

 private:
  Op _op;

  E _e;
};

template <typename Op, typename E>
LambdaMonoid(Op _op, E _e) -> LambdaMonoid<decltype(_e()), Op, E>;

/*
struct Monoid {
  using S = ?;
  static constexpr S op(const S& a, const S& b) {}
  static constexpr S e() {}
};
*/

template <typename Monoid>
struct SegmentTree {
  using S = typename Monoid::S;

 private:
  int n, sz;

  vector<S> seg;

  Monoid m;

 public:
  SegmentTree() = default;

  explicit SegmentTree(Monoid m, int n) : m(m), n(n) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, m.e());
  }

  explicit SegmentTree(Monoid m, const vector<S> &v)
      : SegmentTree(m, (int)v.size()) {
    build(v);
  }

  void build(const vector<S> &v) {
    assert(n == (int)v.size());
    for (int k = 0; k < n; k++) seg[k + sz] = v[k];
    for (int k = sz - 1; k > 0; k--) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void set(int k, const S &x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  S get(int k) const { return seg[k + sz]; }

  S operator[](int k) const { return get(k); }

  void apply(int k, const S &x) {
    k += sz;
    seg[k] = m.op(seg[k], x);
    while (k >>= 1) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  S prod(int l, int r) const {
    if (l >= r) return m.e();
    S L = m.e(), R = m.e();
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
      if (l & 1) L = m.op(L, seg[l++]);
      if (r & 1) R = m.op(seg[--r], R);
    }
    return m.op(L, R);
  }

  S all_prod() const { return seg[1]; }

  template <typename C>
  int find_first(int l, const C &check) const {
    if (l >= n) return n;
    l += sz;
    S sum = m.e();
    do {
      while ((l & 1) == 0) l >>= 1;
      if (check(m.op(sum, seg[l]))) {
        while (l < sz) {
          l <<= 1;
          auto nxt = m.op(sum, seg[l]);
          if (not check(nxt)) {
            sum = nxt;
            l++;
          }
        }
        return l + 1 - sz;
      }
      sum = m.op(sum, seg[l++]);
    } while ((l & -l) != l);
    return n;
  }

  template <typename C>
  int find_last(int r, const C &check) const {
    if (r <= 0) return -1;
    r += sz;
    S sum = m.e();
    do {
      r--;
      while (r > 1 and (r & 1)) r >>= 1;
      if (check(m.op(seg[r], sum))) {
        while (r < sz) {
          r = (r << 1) + 1;
          auto nxt = m.op(seg[r], sum);
          if (not check(nxt)) {
            sum = nxt;
            r--;
          }
        }
        return r - sz;
      }
      sum = m.op(seg[r], sum);
    } while ((r & -r) != r);
    return -1;
  }
};


struct UnionFind {
  vector<int> data;

  UnionFind() = default;

  explicit UnionFind(size_t sz) : data(sz, -1) {}

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if (data[k] < 0) return (k);
    return data[k] = find(data[k]);
  }

  int size(int k) { return -data[find(k)]; }

  bool same(int x, int y) { return find(x) == find(y); }

  vector<vector<int> > groups() {
    int n = (int)data.size();
    vector<vector<int> > ret(n);
    for (int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(remove_if(begin(ret), end(ret),
                        [&](const vector<int> &v) { return v.empty(); }),
              end(ret));
    return ret;
  }
};
/*****************  Debug  *************************************************/
#ifdef LOCAL

#define debug(x) cerr << #x << ": " << (x) << endl;
#else
#define debug(x)
#endif

#ifdef LOCAL
template<typename T> void debug_vector(const vector<T>& v) {
    cerr << "[ ";
    for (const auto& x : v) cerr << x << " ";
    cerr << "]" << endl;
}
template<typename T, typename U> void debug_map(const map<T, U>& m) {
    cerr << "{ ";
    for (const auto& [key, val] : m) cerr << key << ": " << val << ", ";
    cerr << "}" << endl;
}
#define debug2d(v) for (const auto& row : (v)) debug_vector(row)
#endif
// }


const int INF = 1e9 + 5;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

/*********** Library Pasting Area   *****************************************/

/**********************************************************************/

#define INCLUDED_MAIN
#include __FILE__
#endif

Submission Info

Judge Result