Submission #57756106

---

Source Code Expand

/*
Author : Hocky Yudhiono
Saturday, September 14, 2024 PM08:17:24
*/

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<LL, LL> PLL;
typedef pair<LL, LL> pll;
typedef long double ld;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second

const double EPS = 1e-9;
const int INFMEM = 63;

// Do dir^1 to get reverse direction
const int dx[8] = {0,0,1,-1,1,-1,1,-1};
const int dy[8] = {1,-1,0,0,1,-1,-1,1};
const char dch[4] = {'R','L','D','U'};

// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;

inline void fasterios(){
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
}
#define endl '\n'
const int MOD = 1000000007;
// const int MOD = 998244353;
const int kMax = 2e5;
vector <LL> bucket[kMax + 5];
LL isi[kMax + 5];
int main(){
  fasterios();
  int n; cin >> n;
  LL ans = 0;
  rep(i,1,n + 1) {
    cin >> isi[i];
    bucket[isi[i]].pb(i);
    if(bucket[isi[i]].size() == 1) {
      // The first one 
      ans += n - i + 1;
    }
  }
  for(int i = 0;i <= n+1;i++){
    reverse(all(bucket[i]));
  }
  LL curans = 0;
  for(int i = 1;i <= n;i++){
    curans += ans;
    // Buang
    ans -= (n - i + 1);
    bucket[isi[i]].pop_back();
    if(bucket[isi[i]].size()) {
      ans += (n - bucket[isi[i]].back() + 1);
    }
  }
  cout << curans << endl;
}

Submission Info

Judge Result