#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
struct fen {
vector <int> t;
int norm;
fen (int n = 0) : norm(n >> 1), t(n + 100) {}
inline void upd (int i, int x) { for (i += norm; i < sz(t); i += (i & -i)) t[i] += x; }
inline int get (int i) { int res = 0; for (i += norm; i; i -= (i & -i)) res += t[i]; return res; }
inline int get (int l, int r) { return get(r) - get(l - 1); }
};
inline void solve () {
int n; cin >> n;
vector <int> a (n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i], --a[i];
map <int, vector <int>> mp;
for (int i = 1; i <= n; ++i) mp[a[i]].pb(i);
const int N = n * 4 + 100;
const int B = 1800;
ll ans = 0;
function <ll(ll, ll, ll)> ff = [&] (ll L, ll R, ll k) {
umin(L, k); umin(R, k);
assert(L <= 10);
ll rett = 0;
for (int xs = 0; xs <= L; ++xs) rett += min(R, k - xs) + 1;
return rett;
};
for (auto &[_, pos] : mp) {
if (sz(pos) > B) {
vector <int> c (n + 1);
fen t (N); t.upd(0, 1);
for (int i = 1; i <= n; ++i) c[i] = c[i - 1] + (a[i] == _ ? +1 : 0);
for (int i = 1; i <= n; ++i) {
ans += t.get(2 * c[i] - i - 1);
t.upd(2 * c[i] - i, 1);
}
}
else {
for (int i = 0; i < sz(pos); ++i) {
for (int j = i; j < sz(pos); ++j) {
int c = j - i + 1;
int len = pos[j] - pos[i] + 1;
int k = 2 * c - len - 1;
int L = (i ? pos[i] - pos[i - 1] - 1 : pos[i] - 1);
int R = (j + 1 < sz(pos) ? pos[j + 1] - pos[j] - 1 : n - pos[j]);
ans += ff(L, R, k);
}
}
}
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}
Compilation message
Main.cpp: In constructor 'fen::fen(long long int)':
Main.cpp:33:13: warning: 'fen::norm' will be initialized after [-Wreorder]
33 | int norm;
| ^~~~
Main.cpp:32:22: warning: 'std::vector<long long int> fen::t' [-Wreorder]
32 | vector <int> t;
| ^
Main.cpp:34:9: warning: when initialized here [-Wreorder]
34 | fen (int n = 0) : norm(n >> 1), t(n + 100) {}
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
288 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
2 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
7744 KB |
Output is correct |
2 |
Correct |
30 ms |
9876 KB |
Output is correct |
3 |
Correct |
16 ms |
5896 KB |
Output is correct |
4 |
Correct |
30 ms |
10560 KB |
Output is correct |
5 |
Correct |
32 ms |
10820 KB |
Output is correct |
6 |
Correct |
37 ms |
11480 KB |
Output is correct |
7 |
Correct |
34 ms |
11444 KB |
Output is correct |
8 |
Correct |
33 ms |
11456 KB |
Output is correct |
9 |
Correct |
34 ms |
11408 KB |
Output is correct |
10 |
Correct |
33 ms |
11308 KB |
Output is correct |
11 |
Correct |
23 ms |
11368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
288 KB |
Output is correct |
11 |
Correct |
2 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
340 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
2 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
352 KB |
Output is correct |
18 |
Correct |
25 ms |
7744 KB |
Output is correct |
19 |
Correct |
30 ms |
9876 KB |
Output is correct |
20 |
Correct |
16 ms |
5896 KB |
Output is correct |
21 |
Correct |
30 ms |
10560 KB |
Output is correct |
22 |
Correct |
32 ms |
10820 KB |
Output is correct |
23 |
Correct |
37 ms |
11480 KB |
Output is correct |
24 |
Correct |
34 ms |
11444 KB |
Output is correct |
25 |
Correct |
33 ms |
11456 KB |
Output is correct |
26 |
Correct |
34 ms |
11408 KB |
Output is correct |
27 |
Correct |
33 ms |
11308 KB |
Output is correct |
28 |
Correct |
23 ms |
11368 KB |
Output is correct |
29 |
Correct |
31 ms |
11412 KB |
Output is correct |
30 |
Correct |
16 ms |
4380 KB |
Output is correct |
31 |
Correct |
39 ms |
7836 KB |
Output is correct |
32 |
Correct |
125 ms |
15336 KB |
Output is correct |
33 |
Correct |
48 ms |
8196 KB |
Output is correct |
34 |
Correct |
46 ms |
8524 KB |
Output is correct |
35 |
Correct |
25 ms |
5964 KB |
Output is correct |
36 |
Correct |
14 ms |
3924 KB |
Output is correct |
37 |
Correct |
16 ms |
4564 KB |
Output is correct |
38 |
Correct |
57 ms |
11336 KB |
Output is correct |
39 |
Correct |
63 ms |
11308 KB |
Output is correct |
40 |
Correct |
58 ms |
11412 KB |
Output is correct |
41 |
Correct |
61 ms |
11344 KB |
Output is correct |
42 |
Correct |
58 ms |
11340 KB |
Output is correct |
43 |
Correct |
115 ms |
11764 KB |
Output is correct |
44 |
Correct |
122 ms |
11796 KB |
Output is correct |
45 |
Correct |
118 ms |
11524 KB |
Output is correct |
46 |
Correct |
116 ms |
11664 KB |
Output is correct |
47 |
Correct |
115 ms |
11712 KB |
Output is correct |
48 |
Correct |
463 ms |
3984 KB |
Output is correct |
49 |
Correct |
468 ms |
4068 KB |
Output is correct |
50 |
Correct |
728 ms |
12500 KB |
Output is correct |
51 |
Correct |
731 ms |
12460 KB |
Output is correct |
52 |
Correct |
249 ms |
3668 KB |
Output is correct |
53 |
Correct |
266 ms |
3560 KB |
Output is correct |
54 |
Correct |
458 ms |
3788 KB |
Output is correct |