| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 697358 | Do_you_copy | Izbori (COCI22_izbori) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
I find it wholesome to be alone the greater part of the time.
To be in company, even with the best, is soon wearisome and dissipating.
I love to be alone.
I never found the companion that was so companionable as solitude.
*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 1;
//const int Mod = 1e9 + 7;
//const ll inf = 0x3f3f3f3f3f3f3f3f;
int n;
vector <int> S[maxN];
int a[maxN];
int dp[maxN];
ll ans;
ll calc(int i, int j, int k){
int l = k - i;
int r = k ;
k = max(0, r - max(j + 1, l - 1));
l = max(l, 0);
r = min(r, j + 1);
if (l > r) return k * (j + 1);
return 1LL * (l + r) * (r - l + 1) / 2 + k * (j + 1);
}
void Light(int c){
for (int i = 0; i < signed(S[c].size()); ++i){
for (int j = i; j < signed(S[c].size()); ++j){
int l = i ? S[c][i - 1] : 0;
int r = (j + 1 == S[c].size()) ? n + 1 : S[c][j + 1];
int k = (j - i + 1) - (S[c][j] - S[c][i] - j + i);
ans += calc(S[c][i] - l - 1, r - S[c][j] - 1, k);
}
}
}
void Heavy(int c){
fill(dp, dp + 2 * n + 2, 0);
int cur = n + 1;
dp[cur] = 1;
for (int i = 1; i <= n; ++i){
if (a[i] == c){
++cur;
dp[cur] += dp[cur - 1];
}
else{
dp[cur] -= dp[cur - 1];
--cur;
}
++dp[cur];
ans += dp[cur - 1];
}
}
void Init(){
cin >> n;
vector <int> node;
for (int i = 1; i <= n; ++i){
cin >> a[i];
node.pb(a[i]);
}
sort(node.begin(), node.end());
node.resize(unique(node.begin(), node.end()) - node.begin());
for (int i = 1; i <= n; ++i){
a[i] = upper_bound(node.begin(), node.end(), a[i]) - node.begin();
S[a[i]].pb(i);
}
for (int i = 1; i <= n; ++i){
if (S[i].empty()) continue;
if (S[i].size() <= 318) Light(i);
else Heavy(i);
}
cout << ans;
}
#define debug
#define taskname "test"
signed main(){
faster
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
int tt = 1;
//cin >> tt;
while (tt--){
Init();
}
if (fopen("timeout.txt", "r")){
ofstream timeout("timeout.txt");
timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
timeout.close();
#ifndef debug
cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
#endif // debug
}
}