#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define pii pair<int, int>
#define pill pair<ll, ll>
#define s second
#define ld long double
using namespace std;
const ll N = 5e5 + 10;
const ll M = 5e6 + 10;
const ll mod = 1e4 + 7;
const ll big = 1e4;
const double eps = 1e-8;
ll t, n, k;
ll a[N];
//start : 9:59
vector<int> g[N], gg;
int kek[8 * N], sz = 0;
int cur_ver = 0;
struct seg {
ll t[8 * N] = {0};
ll c[8 * N] = {0};
int d[8 * N] = {0};
int ver[8 * N] = {0};
void push(ll v, ll l, ll r) {
if(ver[v] != cur_ver)t[v] = 0, c[v] = 0, d[v] = 0, ver[v] = cur_ver;
t[v] = t[v] + c[v] * (r - l + 1) + d[v] * (r - l + 1) * (r - l + 2) / 2ll;
if(l != r) {
int m = (l + r) >> 1ll;
if(ver[v * 2] != cur_ver)t[v * 2] = 0, c[v * 2] = 0, d[v * 2] = 0, ver[v * 2] = cur_ver;
if(ver[v * 2 + 1] != cur_ver)t[v * 2 + 1] = 0, c[v * 2 + 1] = 0, d[v * 2 + 1] = 0, ver[v * 2 + 1] = cur_ver;
c[v * 2] += c[v];
c[v * 2 + 1] += c[v] + d[v] * ((m + 1) - l);
d[v * 2] += d[v];
d[v * 2 + 1] += d[v];
}
c[v] = 0, d[v] = 0;
return;
}
void upd1(ll l, ll r, ll v = 1, ll tl = 0, ll tr = 2 * n) {
if(l > tr || tl > r)
return;
push(v, tl, tr);
if(l <= tl && tr <= r) {
c[v] += (tl - l);
d[v] += 1;
push(v, tl, tr);
return;
}
ll m = (tl + tr) >> 1ll;
upd1(l , r, v * 2, tl, m);
upd1(l , r, v * 2 + 1, m + 1, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
void upd2(ll l, ll r, ll z, ll v = 1, ll tl = 0, ll tr = 2 * n) {
if(l > tr || tl > r)
return;
push(v, tl, tr);
if(l <= tl && tr <= r) {
c[v] += z;
push(v, tl, tr);
return;
}
ll m = (tl + tr) >> 1ll;
upd2(l , r, z, v * 2, tl, m);
upd2(l , r, z, v * 2 + 1, m + 1, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
ll get(ll l, ll r, ll v = 1, ll tl = 0, ll tr = 2 * n) {
if(l > tr || tl > r)
return 0;
push(v, tl, tr);
if(l <= tl && tr <= r) {
return t[v];
}
ll m = (tl + tr) >> 1ll;
return get(l , r, v * 2, tl, m) + get(l , r, v * 2 + 1, m + 1, tr);
}
} rt;
int main() {
speed;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
g[a[i]].pb(i);
}
ll ans = 0;
for(int i = 1; i <= k; i++) {
if(g[i].size() == 0)continue;
cur_ver++;
rt.upd1(-g[i][0] + 1 + n, n);
rt.upd2(n + 1, 2 * n, n - (n - g[i][0]));
for(int j = 0; j < g[i].size(); j++) {
int cnt = j + 1;
int cur = g[i][j];
int nxt = n + 1;
if(g[i].size() != j + 1)
nxt = g[i][j + 1];
ans = (ans + rt.get(2 * cnt - nxt + n, 2 * cnt - cur + n - 1));
rt.upd1(2 * cnt - (nxt - 1) + n, 2 * cnt - cur + n);
rt.upd2(2 * cnt - cur + n + 1, 2 * n, nxt - cur);
}
}
cout << ans << "\n";
}
/*
6 1
3 1 5 3 7 5
4 6 4
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int j = 0; j < g[i].size(); j++) {
| ~~^~~~~~~~~~~~~
Main.cpp:105:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
105 | if(g[i].size() != j + 1)
| ~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
24268 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
24268 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
14576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
21 ms |
24268 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
