// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
struct Node {
Node *l, *r;
ll val, sum, mset = INF, madd = 0;
int lo, hi;
Node(int L, int R) : lo(L), hi(R) {
if (hi - lo == 1)
val = sum = 0;
else {
int mid = (lo + hi) / 2;
l = new Node(lo, mid);
r = new Node(mid, hi);
update();
}
}
void update() {
int mid = (lo + hi) / 2;
sum = l->sum + r->sum;
val = l->val + r->val + l->sum * (hi - mid);
}
pll query(int L, int R) {
if (hi <= L || R <= lo) return {0, 0};
if (L <= lo && hi <= R) {
// cout << "L = " << lo << " R = " << hi << " cur_val = " << val << " cur_sum = " << sum << endl;
return {val + sum * (R - hi), sum};
}
push();
int mid = (lo + hi) / 2;
pll lpair = l->query(L, R), rpair = r->query(L, R);
ll right_len = max(0, R - mid);
ll cur_sum = lpair.second + rpair.second;
ll cur_val = lpair.first + rpair.first;
// cout << "L = " << lo << " R = " << hi << " cur_val = " << cur_val << " cur_sum = " << cur_sum << endl;
return {cur_val, cur_sum};
}
void set(int L, int R, ll x) {
if (hi <= L || R <= lo) return;
if (L <= lo && hi <= R) {
madd = 0;
mset = x;
sum = x * ll(hi - lo);
val = x * ll(hi - lo) * ll(hi - lo + 1) / 2;
return;
}
push();
l->set(L, R, x);
r->set(L, R, x);
update();
}
void add(int L, int R, ll x) {
if (hi <= L || R <= lo) return;
if (L <= lo && hi <= R) {
if (mset != INF)
mset += x;
else
madd += x;
// cout << "lo = " << lo << " hi = " << hi << endl;
sum += x * ll(hi - lo);
val += x * ll(hi - lo) * ll(hi - lo + 1) / 2;
return;
}
push();
l->add(L, R, x);
r->add(L, R, x);
update();
}
void push() {
if (mset != INF) {
if (hi - lo != 1) {
l->set(lo, hi, mset);
r->set(lo, hi, mset);
}
mset = INF;
} else if (madd) {
if (hi - lo != 1) {
l->add(lo, hi, madd);
r->add(lo, hi, madd);
}
madd = 0;
}
}
};
const ll seg_size = 32;
int n, arr[200005];
umap<int, vi> dishes;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n;
rep(i, 0, n) {
cin >> arr[i];
dishes[arr[i]].pb(i);
}
ll ans = 0;
Node segtree(0, seg_size);
trav(item, dishes) {
int dish;
vi people;
tie(dish, people) = item;
people.pb(n);
//debug(dish);
int prefix = seg_size / 2;
segtree.set(0, seg_size, 0);
segtree.add(prefix, prefix + (people[0]) + 1, 1);
rep(i, 0, sz(people) - 1) {
ll prev = ans;
++prefix;
int cur_pos = people[i], next_pos = people[i + 1], len = next_pos - cur_pos;
ll val = 0, sum = 0;
//cout << "i = " << i << " prefix = " << prefix << " len = " << len << endl;
tie(val, sum) = segtree.query(prefix - len, prefix);
//cout<<endl;
ans += val;
//cout << "val = " << val << endl;
tie(val, sum) = segtree.query(0, prefix - len);
//cout<<endl;
ans += sum * len;
//cout << "sum = " << sum << endl;
segtree.add(prefix - (len - 1), prefix + 1, 1);
//cout << endl<<endl;
prefix -= len - 1;
}
//cout << endl;
}
/*ll real_ans=0;
rep(i,0,n) {
umap<int,int>cnt;
int mx=0;
rep(j,i,n){
++cnt[arr[j]];
mx=max(mx,cnt[arr[j]]);
if(mx>(j-i+1)/2) ++real_ans;
}
}*/
cout << ans << endl;
return 0;
}
Compilation message
Main.cpp: In member function 'pll Node::query(int, int)':
Main.cpp:65:12: warning: unused variable 'right_len' [-Wunused-variable]
65 | ll right_len = max(0, R - mid);
| ^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define rep(i, a, b) for (int i = (a); i < (b); ++i)
| ^
Main.cpp:158:9: note: in expansion of macro 'rep'
158 | rep(i, 0, sz(people) - 1) {
| ^~~
Main.cpp:159:16: warning: unused variable 'prev' [-Wunused-variable]
159 | ll prev = ans;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
2064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
