#include <bits/stdc++.h>
using namespace std;
long long N,A[200005];
vector<long long> A1, lst[200005];
struct node {
long long s,e,m,v; pair<long long,long long> lazy; node *l, *r;
node (long long S, long long E) {
s = S, e = E, m = (s+e)/2, v = 0, lazy = make_pair(0,0);
if (s != e) l = new node(s,m), r = new node(m+1,e);
}
void propo() {
if (lazy == make_pair(0ll,0ll)) return;
v += (e-s+1) * (e-s) / 2 * lazy.first + (e-s+1) * lazy.second;
if (s != e) l->lazy.first += lazy.first, l->lazy.second += lazy.second, r->lazy.first += lazy.first, r->lazy.second += lazy.second;
lazy = make_pair(0,0);
}
void update (long long x, long long y, long long a, long long b) {
propo();
if (s == x && e == y) lazy.first += a, lazy.second += b;
else {
if (y <= m) l -> update(x,y,a,b);
else if (x > m) r -> update(x,y,a,b);
else l -> update(x,m,a,b), r -> update(m+1,y,a,b+(m-x+1)*a);
l->propo(), r->propo();
v = l->v + r->v;
}
}
long long query (long long x, long long y) {
propo();
if (s == x && e == y) return v;
else if (y <= m) return l -> query(x,y);
else if (x > m) return r -> query(x,y);
else return l->query(x,m) + r->query(m+1,y);
}
}*root;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N;
for (long long i = 0; i < N; ++i) {
cin >> A[i];
A1.push_back(A[i]);
}
sort(A1.begin(),A1.end());
A1.resize(unique(A1.begin(),A1.end())-A1.begin());
for (long long i = 0; i < N; ++i) {
A[i] = lower_bound(A1.begin(),A1.end(),A[i])-A1.begin();
lst[A[i]].push_back(lst[A[i]].size()*2-i+1);
}
root = new node(0,N*2);
long long ans = 0;
for (long long i = 0; i < N; ++i) if (!lst[i].empty()) {
root -> update(N+lst[i][0]-1,N,1,1);
root -> update(N+1,N*2,0,2-lst[i][0]);
for (long long j = 1; j < lst[i].size(); ++j) {
ans += root -> query(N+lst[i][j]-2,N+lst[i][j-1]-1);
root -> update(N+lst[i][j]-1,N+lst[i][j-1],1,1);
root -> update(N+lst[i][j-1]+1,N*2,0,lst[i][j-1]-lst[i][j]+2);
}
ans += root -> query(lst[i].size()*2-1,N+lst[i].back()-1);
root -> update(N+lst[i][0]-1,N,-1,-1);
root -> update(N+1,N*2,0,lst[i][0]-2);
for (long long j = 1; j < lst[i].size(); ++j) {
root -> update(N+lst[i][j]-1,N+lst[i][j-1],-1,-1);
root -> update(N+lst[i][j-1]+1,N*2,0,lst[i][j]-lst[i][j-1]-2);
}
}
cout << ans;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:57:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (long long j = 1; j < lst[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:65:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (long long j = 1; j < lst[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
160 ms |
50176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5068 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
