#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 10;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
return ((1LL * a - b) % mod + mod) % mod;
}
ll add(ll a, ll b){
return ((1LL * a + b) % mod + mod) % mod;
}
ll binpow(ll x, ll step){
ll res = 1LL;
while(step){
if(step & 1) res = um(res, x);
x = um(x, x);
step /= 2;
}
return res;
}
int arr[N], b[N], n;
vector <int> vec[N];
struct segtree {
ll sz;
vector <ll> tree, cnt, com;
vector <bool> z;
void cl(ll x, ll lx, ll rx){
if(rx - lx == 1){
if(z[x]) cnt[x] = com[x] = tree[x] = z[x] = 0;
return;
}
if(z[x] == true){
cnt[x] = com[x] = tree[x] = 0;
z[2 * x + 1] = z[2 * x + 2] = true;
z[x] = false;
}
}
void prop(ll x, ll lx, ll rx){
if(rx - lx == 1) return;
ll mid = (lx + rx) / 2;
cl(2 * x + 1, lx, mid);
cl(2 * x + 2, mid, rx);
com[2 * x + 1] += com[x];
com[2 * x + 2] = com[2 * x + 2] + com[x] + cnt[x] * (rx - lx) / 2;
cnt[2 * x + 1] += cnt[x];
cnt[2 * x + 2] += cnt[x];
cnt[x] = com[x] = tree[x] = 0;
}
void init(ll n){
sz = 1;
while(sz < n) sz *= 2;
tree.assign(2 * sz - 1, 0LL);
cnt.assign(2 * sz - 1, 0LL);
com.assign(2 * sz - 1, 0LL);
z.assign(2 * sz - 1, false);
}
void find(ll x, ll l, ll r){
if(r - l == 1){
tree[x] = com[x] + cnt[x];
} else{
tree[x] = com[x] * (r - l) + cnt[x] * ((r - l) * (r - l + 1) / 2LL);
if(z[2 * x + 1] == false) tree[x] += tree[2 * x + 1];
if(z[2 * x + 2] == false) tree[x] += tree[2 * x + 2];
}
}
ll get(ll l, ll r, ll x, ll lx, ll rx){
cl(x, lx, rx);
if(lx >= r || l >= rx) return 0LL;
if(l <= lx && rx <= r){
find(x, lx, rx);
return tree[x];
}
prop(x, lx, rx);
ll mid = (lx + rx) / 2;
ll s1 = get(l, r, 2 * x + 1, lx, mid);
ll s2 = get(l, r, 2 * x + 2, mid, rx);
return s1 + s2;
}
ll get(ll l, ll r){
return get(l, r, 0, 0, sz);
}
void upd(ll l, ll r, ll x, ll lx, ll rx){
cl(x, lx, rx);
if(l >= rx || lx >= r) return;
if(l <= lx && rx <= r){
com[x] += (lx - l);
cnt[x]++;
find(x, lx, rx);
return;
}
prop(x, lx, rx);
ll mid = (lx + rx) / 2;
upd(l, r, 2 * x + 1, lx, mid);
upd(l, r, 2 * x + 2, mid, rx);
tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
}
void upd(ll l, ll r){
upd(l, r, 0, 0, sz);
}
void upd2(ll l, ll r, ll s, ll x, ll lx, ll rx){
cl(x, lx, rx);
if(l >= rx || lx >= r) return;
if(l <= lx && rx <= r){
com[x] += s;
find(x, lx, rx);
return;
}
prop(x, lx, rx);
ll mid = (lx + rx) / 2;
upd2(l, r, s, 2 * x + 1, lx, mid);
upd2(l, r, s, 2 * x + 2, mid, rx);
tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
}
void upd2(ll l, ll s){
upd2(l, sz, s, 0, 0, sz);
}
void write(){
for(int i = 0; i < 2 * sz - 1; i++){
cout << i << " " <<tree[i] << " "<< com[i] << " "<< cnt[i] << " "<<z[i] << endl;
}
cout << endl;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
b[i] = arr[i];
}
sort(b, b + n);
int sz = unique(b, b + n) - b;
for(int i = 0; i < sz; i++){
vec[i].pb(-1);
}
for(int i = 0; i < n; i++){
arr[i] = lower_bound(b, b + sz, arr[i]) - b;
vec[arr[i]].pb(i);
}
for(int i = 0; i < sz; i++){
vec[i].pb(n);
}
segtree obj;
obj.init(2 * n + 5);
ll ans = 0;
for(int i = 0, plus; i < sz; i++){
plus = 0;
for(int index = 0; index < (int)vec[i].size() - 1; index++){
int pref = plus * 2 - vec[i][index] - 1;
plus++;
int from = pref - (vec[i][index + 1] - vec[i][index] - 1) + n, to = pref + 1 + n;
ll local = obj.get(from, to);
ans += local;
obj.upd(from + 1, to + 1);
obj.upd2(to + 1, to - from);
}
obj.z[0] = true;
}
cout << ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
5212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
5212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
155 ms |
31436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
5212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
