# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1011244 |
2024-06-30T07:42:18 Z |
0pt1mus23 |
Izbori (COCI22_izbori) |
C++14 |
|
1832 ms |
55888 KB |
/*
not my sol, edu
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 2e5+10, inf = LLONG_MAX, prime = 1453;
int arr[sze];
int brr[sze];
int dac(int l,int r){
if(l==r){
return 1;
}
if(l>r){
return 0;
}
int ans=0;
int mid = (l+r)/2;
set<int> cand;
map<int,int> cnt;
for(int i = mid-1;i>=l;i--){
++cnt[arr[i]];
if(cnt[arr[i]]> (mid-i)/2){
cand.ins(arr[i]);
}
}
cnt.clear();
for(int i = mid;i<=r;i++){
++cnt[arr[i]];
if(cnt[arr[i]]>(i-mid+1)/2){
cand.ins(arr[i]);
}
}
for(auto v:cand){
for(int i=l;i<=r;i++){
if(arr[i]==v){
brr[i]=+1;
}
else{
brr[i]=-1;
}
}
cnt.clear();
int sum=0;
++cnt[0];
for(int i=l;i<mid;i++){
sum+=brr[i];
++cnt[sum];
}
int upto = (r-l+1);
for(int i = -upto;i<=upto;i++){
cnt[i]+=cnt[i-1];
}
for(int i = mid;i<=r;i++){
sum+=brr[i];
ans+=cnt[sum-1];
}
}
// cout<<l<<" "<<r<<" "<<ans<<endl;
return ans + dac(l,mid-1) + dac(mid+1,r);
}
void mal(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
cout<<dac(1,n)<<endl;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
clock_t z = clock();
int tt = 1;
// cin>>tt;
while(tt--){
mal();
}
// cerr<<(double)(clock() - z) / CLOCKS_PER_SEC <<endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:86:13: warning: unused variable 'z' [-Wunused-variable]
86 | clock_t z = clock();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
7 ms |
984 KB |
Output is correct |
10 |
Correct |
7 ms |
860 KB |
Output is correct |
11 |
Correct |
10 ms |
776 KB |
Output is correct |
12 |
Correct |
9 ms |
860 KB |
Output is correct |
13 |
Correct |
7 ms |
992 KB |
Output is correct |
14 |
Correct |
7 ms |
860 KB |
Output is correct |
15 |
Correct |
7 ms |
860 KB |
Output is correct |
16 |
Correct |
7 ms |
992 KB |
Output is correct |
17 |
Correct |
4 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
911 ms |
36012 KB |
Output is correct |
2 |
Correct |
1209 ms |
47052 KB |
Output is correct |
3 |
Correct |
681 ms |
27492 KB |
Output is correct |
4 |
Correct |
1332 ms |
49232 KB |
Output is correct |
5 |
Correct |
1368 ms |
51016 KB |
Output is correct |
6 |
Correct |
1471 ms |
54064 KB |
Output is correct |
7 |
Correct |
1475 ms |
54096 KB |
Output is correct |
8 |
Correct |
1561 ms |
54064 KB |
Output is correct |
9 |
Correct |
1562 ms |
54064 KB |
Output is correct |
10 |
Correct |
1528 ms |
54068 KB |
Output is correct |
11 |
Correct |
958 ms |
53840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
3 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
7 ms |
984 KB |
Output is correct |
10 |
Correct |
7 ms |
860 KB |
Output is correct |
11 |
Correct |
10 ms |
776 KB |
Output is correct |
12 |
Correct |
9 ms |
860 KB |
Output is correct |
13 |
Correct |
7 ms |
992 KB |
Output is correct |
14 |
Correct |
7 ms |
860 KB |
Output is correct |
15 |
Correct |
7 ms |
860 KB |
Output is correct |
16 |
Correct |
7 ms |
992 KB |
Output is correct |
17 |
Correct |
4 ms |
856 KB |
Output is correct |
18 |
Correct |
911 ms |
36012 KB |
Output is correct |
19 |
Correct |
1209 ms |
47052 KB |
Output is correct |
20 |
Correct |
681 ms |
27492 KB |
Output is correct |
21 |
Correct |
1332 ms |
49232 KB |
Output is correct |
22 |
Correct |
1368 ms |
51016 KB |
Output is correct |
23 |
Correct |
1471 ms |
54064 KB |
Output is correct |
24 |
Correct |
1475 ms |
54096 KB |
Output is correct |
25 |
Correct |
1561 ms |
54064 KB |
Output is correct |
26 |
Correct |
1562 ms |
54064 KB |
Output is correct |
27 |
Correct |
1528 ms |
54068 KB |
Output is correct |
28 |
Correct |
958 ms |
53840 KB |
Output is correct |
29 |
Correct |
951 ms |
55524 KB |
Output is correct |
30 |
Correct |
257 ms |
10576 KB |
Output is correct |
31 |
Correct |
630 ms |
21140 KB |
Output is correct |
32 |
Correct |
1832 ms |
51828 KB |
Output is correct |
33 |
Correct |
588 ms |
22604 KB |
Output is correct |
34 |
Correct |
683 ms |
23496 KB |
Output is correct |
35 |
Correct |
416 ms |
15440 KB |
Output is correct |
36 |
Correct |
229 ms |
9296 KB |
Output is correct |
37 |
Correct |
306 ms |
11280 KB |
Output is correct |
38 |
Correct |
1683 ms |
54052 KB |
Output is correct |
39 |
Correct |
1562 ms |
54016 KB |
Output is correct |
40 |
Correct |
1767 ms |
53824 KB |
Output is correct |
41 |
Correct |
1643 ms |
54100 KB |
Output is correct |
42 |
Correct |
1639 ms |
53972 KB |
Output is correct |
43 |
Correct |
1609 ms |
55644 KB |
Output is correct |
44 |
Correct |
1470 ms |
55888 KB |
Output is correct |
45 |
Correct |
1539 ms |
55648 KB |
Output is correct |
46 |
Correct |
1532 ms |
55636 KB |
Output is correct |
47 |
Correct |
1469 ms |
55648 KB |
Output is correct |
48 |
Correct |
1721 ms |
54116 KB |
Output is correct |
49 |
Correct |
1675 ms |
54492 KB |
Output is correct |
50 |
Correct |
1706 ms |
54100 KB |
Output is correct |
51 |
Correct |
1672 ms |
54132 KB |
Output is correct |
52 |
Correct |
1620 ms |
54408 KB |
Output is correct |
53 |
Correct |
1635 ms |
54356 KB |
Output is correct |
54 |
Correct |
1537 ms |
54364 KB |
Output is correct |