이 제출은 이전 버전의 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){
i = min(i, k - 1);
j = min(j, k - 1);
ll res = 0;
if (k <= 0) return 0;
int i1 = min(i, k - j - 1);
res += 1LL * (j + 1) * max(0LL, i1 + 1);
i1 = max(i1 + 1, 0LL);
j = k - 1 - i1;
if (j < 0) return res;
int aa = i1 + 1;
int bb = j + 1;
int x = min(i + 1 - aa, bb - 1);
// (i1 -> i) * (j - 1 -> j - x)
res += 1LL * (x + 1) * aa * bb + x * (x + 1) * (bb - aa) / 2 + x * (x + 1) * (2 * x + 1) / 6;
return res;
}
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() <= 0) 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
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void Light(long long int)':
Main.cpp:49:28: 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]
49 | int r = (j + 1 == S[c].size()) ? n + 1 : S[c][j + 1];
| ~~~~~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |