| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 902173 |
2024-01-10T06:44:55 Z |
Isam |
Izbori (COCI22_izbori) |
C++17 |
|
3000 ms |
6984 KB |
#include<bits/stdc++.h>
using namespace std;
constexpr int sz = 300005;
int N, A[sz];
long long pref[sz], tree[sz];
unordered_set<int> st;
inline void update(int pos, long long val){
while(pos <= N + 5){
tree[pos] += val;
pos += (pos & (-pos));
}
return;
}
long long get_ans(int l, int r){
if(l != 1) return get_ans(1, r) - get_ans(1, l - 1);
long long res(0);
while(r > 0){
res += tree[r];
r -= (r & (-r));
}
return res;
}
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N;
for(register int i = 1; i <= N; ++i){
cin >> A[i];
st.insert(A[i]);
}
long long ans(0);
for(auto &tot : st){
for(register int i = 1; i <= N + 10; ++i) tree[i] = 0;
long long mn = N + 5;
for(register int i = 1; i <= N; ++i){
pref[i] = pref[i - 1] + (tot == A[i] ? 1 : -1);
mn = min(mn, pref[i]);
}
mn = abs(mn) + 5;
update(mn, 1);
for(register int i = 1; i <= N ;++i){
pref[i] += mn;
update(pref[i], 1);
ans += get_ans(1, pref[i] - 1);
}
}
cout << ans << '\n';
return 0;
}
/*
1 1 2 1 2
-1 -1 1 -1 1
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:32:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
32 | for(register int i = 1; i <= N; ++i){
| ^
Main.cpp:38:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
38 | for(register int i = 1; i <= N + 10; ++i) tree[i] = 0;
| ^
Main.cpp:40:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
40 | for(register int i = 1; i <= N; ++i){
| ^
Main.cpp:46:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
46 | for(register int i = 1; i <= N ;++i){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
360 KB |
Output is correct |
| 2 |
Correct |
1 ms |
356 KB |
Output is correct |
| 3 |
Correct |
0 ms |
356 KB |
Output is correct |
| 4 |
Correct |
0 ms |
356 KB |
Output is correct |
| 5 |
Correct |
0 ms |
360 KB |
Output is correct |
| 6 |
Correct |
1 ms |
612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
360 KB |
Output is correct |
| 2 |
Correct |
1 ms |
356 KB |
Output is correct |
| 3 |
Correct |
0 ms |
356 KB |
Output is correct |
| 4 |
Correct |
0 ms |
356 KB |
Output is correct |
| 5 |
Correct |
0 ms |
360 KB |
Output is correct |
| 6 |
Correct |
1 ms |
612 KB |
Output is correct |
| 7 |
Correct |
11 ms |
360 KB |
Output is correct |
| 8 |
Correct |
1 ms |
360 KB |
Output is correct |
| 9 |
Correct |
1 ms |
360 KB |
Output is correct |
| 10 |
Correct |
1 ms |
488 KB |
Output is correct |
| 11 |
Correct |
1 ms |
360 KB |
Output is correct |
| 12 |
Correct |
2 ms |
360 KB |
Output is correct |
| 13 |
Correct |
2 ms |
360 KB |
Output is correct |
| 14 |
Correct |
1 ms |
360 KB |
Output is correct |
| 15 |
Correct |
1 ms |
360 KB |
Output is correct |
| 16 |
Correct |
1 ms |
360 KB |
Output is correct |
| 17 |
Correct |
1 ms |
360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
4456 KB |
Output is correct |
| 2 |
Correct |
19 ms |
4884 KB |
Output is correct |
| 3 |
Correct |
11 ms |
3944 KB |
Output is correct |
| 4 |
Correct |
24 ms |
4968 KB |
Output is correct |
| 5 |
Correct |
23 ms |
5216 KB |
Output is correct |
| 6 |
Correct |
23 ms |
5232 KB |
Output is correct |
| 7 |
Correct |
23 ms |
5180 KB |
Output is correct |
| 8 |
Correct |
20 ms |
5208 KB |
Output is correct |
| 9 |
Correct |
20 ms |
5208 KB |
Output is correct |
| 10 |
Correct |
22 ms |
5416 KB |
Output is correct |
| 11 |
Correct |
15 ms |
5400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
360 KB |
Output is correct |
| 2 |
Correct |
1 ms |
356 KB |
Output is correct |
| 3 |
Correct |
0 ms |
356 KB |
Output is correct |
| 4 |
Correct |
0 ms |
356 KB |
Output is correct |
| 5 |
Correct |
0 ms |
360 KB |
Output is correct |
| 6 |
Correct |
1 ms |
612 KB |
Output is correct |
| 7 |
Correct |
11 ms |
360 KB |
Output is correct |
| 8 |
Correct |
1 ms |
360 KB |
Output is correct |
| 9 |
Correct |
1 ms |
360 KB |
Output is correct |
| 10 |
Correct |
1 ms |
488 KB |
Output is correct |
| 11 |
Correct |
1 ms |
360 KB |
Output is correct |
| 12 |
Correct |
2 ms |
360 KB |
Output is correct |
| 13 |
Correct |
2 ms |
360 KB |
Output is correct |
| 14 |
Correct |
1 ms |
360 KB |
Output is correct |
| 15 |
Correct |
1 ms |
360 KB |
Output is correct |
| 16 |
Correct |
1 ms |
360 KB |
Output is correct |
| 17 |
Correct |
1 ms |
360 KB |
Output is correct |
| 18 |
Correct |
19 ms |
4456 KB |
Output is correct |
| 19 |
Correct |
19 ms |
4884 KB |
Output is correct |
| 20 |
Correct |
11 ms |
3944 KB |
Output is correct |
| 21 |
Correct |
24 ms |
4968 KB |
Output is correct |
| 22 |
Correct |
23 ms |
5216 KB |
Output is correct |
| 23 |
Correct |
23 ms |
5232 KB |
Output is correct |
| 24 |
Correct |
23 ms |
5180 KB |
Output is correct |
| 25 |
Correct |
20 ms |
5208 KB |
Output is correct |
| 26 |
Correct |
20 ms |
5208 KB |
Output is correct |
| 27 |
Correct |
22 ms |
5416 KB |
Output is correct |
| 28 |
Correct |
15 ms |
5400 KB |
Output is correct |
| 29 |
Correct |
24 ms |
6984 KB |
Output is correct |
| 30 |
Execution timed out |
3013 ms |
5044 KB |
Time limit exceeded |
| 31 |
Halted |
0 ms |
0 KB |
- |
