#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=2e5;
int n, a[mxN];
map<int, vector<int>> mp;
ll ans;
struct {
int sum[1<<20], lz[1<<20];
ll isum[1<<20];
void psh(int u, int l, int r) {
if (lz[u]) {
sum[u]+=lz[u]*(r-l+1);
isum[u]+=(ll)lz[u]*(r-l+1)*(l+r)/2;
if (l!=r)
lz[2*u]+=lz[u], lz[2*u+1]+=lz[u];
lz[u]=0;
}
}
void upd(int ql, int qr, int x, int u=1, int l=0, int r=2*n) {
psh(u, l, r);
if (l>qr||r<ql)
return;
if (ql<=l&&r<=qr) {
lz[u]+=x;
psh(u, l, r);
return;
}
int mid=(l+r)/2;
upd(ql, qr, x, 2*u, l, mid);
upd(ql, qr, x ,2*u+1, mid+1, r);
sum[u]=sum[2*u]+sum[2*u+1];
isum[u]=isum[2*u]+isum[2*u+1];
}
ll qry(int ql, int qr, int t, int u=1, int l=0, int r=2*n) {
psh(u, l, r);
if (l>qr||r<ql)
return 0;
if (ql<=l&&r<=qr)
return t==0?sum[u]:isum[u];
int mid=(l+r)/2;
return qry(ql, qr, t, 2*u, l, mid)+qry(ql, qr, t, 2*u+1, mid+1, r);
}
} st;
void solve(vector<int> v) {
int pref=n;
vector<ar<int, 2>> rb;
if (v[0]) {
st.upd(n-v[0], n-1, 1);
rb.push_back({n-v[0], n-1});
pref-=v[0];
}
for (int i=0; i<v.size(); ++i) {
++pref;
ans+=st.qry(0, pref-1, 0);
//cout << ans << "\n";
st.upd(pref, pref, 1);
rb.push_back({pref, pref});
if (i+1<v.size()&&v[i]+1<v[i+1]||i+1==v.size()&&v[i]<n-1) {
int len=(i+1==v.size()?n-1:v[i+1]-1)-v[i];
//cout << "len " << len << endl;
ans+=st.qry(0, pref-len-1, 0);
ans+=(pref-1)*st.qry(pref-len, pref-2, 0)-st.qry(pref-len, pref-2, 1);
st.upd(pref-len, pref-1, 1);
rb.push_back({pref-len, pref-1});
pref-=len;
}
//cout << ans << "\n";
}
for (ar<int, 2> x : rb)
st.upd(x[0], x[1], -1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i=0; i<n; ++i) {
cin >> a[i];
mp[a[i]].push_back(i);
}
st.upd(n, n, 1);
for (auto x : mp)
solve(x.second); // , cout << ans << "\n";
cout << ans;
return 0;
}
Compilation message
Main.cpp: In function 'void solve(std::vector<int>)':
Main.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i=0; i<v.size(); ++i) {
| ~^~~~~~~~~
Main.cpp:64:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if (i+1<v.size()&&v[i]+1<v[i+1]||i+1==v.size()&&v[i]<n-1) {
| ~~~^~~~~~~~~
Main.cpp:64:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if (i+1<v.size()&&v[i]+1<v[i+1]||i+1==v.size()&&v[i]<n-1) {
| ~~~^~~~~~~~~~
Main.cpp:64:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
64 | if (i+1<v.size()&&v[i]+1<v[i+1]||i+1==v.size()&&v[i]<n-1) {
Main.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | int len=(i+1==v.size()?n-1:v[i+1]-1)-v[i];
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
3868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
