# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
851461 |
2023-09-19T21:14:59 Z |
epicci23 |
Izbori (COCI22_izbori) |
C++17 |
|
2447 ms |
12092 KB |
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n"
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 4e5 + 5;
int fw[N];
void upd(int c){
for(;c<N;c+=c&-c) fw[c]++;
}
int query(int c,int res=0){
for(;c;c-=c&-c) res+=fw[c];
return res;
}
void solve(){
int n;
cin >> n;
int ar[n+1];
for(int i=1;i<=n;i++){
cin >> ar[i];
}
int ans=0;
vector<int> zip;
for(int i=1;i<=n;i++) zip.pb(ar[i]);
sort(all(zip));
zip.erase(unique(all(zip)),zip.end()); // dont forget std::unique function!
for(int i=1;i<=n;i++) ar[i]=upper_bound(all(zip),ar[i])-zip.begin();
const int BL = 500;
int freq[n+1];
memset(freq,0,sizeof(freq));
for(int i=1;i<=n;i++) freq[ar[i]]++;
for(int i=1;i<=n;i++){
if(freq[i]<BL) continue;
int nar[n+1];
for(int j=1;j<=n;j++){
if(ar[j]==i) nar[j]=1;
else nar[j]=-1;
}
memset(fw,0,sizeof(fw));
int cur=0;
upd(cur+n);
for(int j=1;j<=n;j++){
cur+=nar[j];
ans+=query(cur+n-1);
upd(cur+n);
}
}
for(int i=1;i<=2*BL;i++){
if(i>n) continue;
int cfreq[n+1];
pair<int,int> coco={-1,-1};
memset(cfreq,0,sizeof(cfreq));
for(int j=1;j<=n;j++){
cfreq[ar[j]]++;
if(j>i) cfreq[ar[j-i]]--;
if(cfreq[ar[j]]>i/2) coco={ar[j],cfreq[ar[j]]};
if(coco.first!=-1 && cfreq[coco.first]<=i/2) coco={-1,-1};
if(j>=i && coco.first!=-1 && freq[coco.first]<BL) ans++;
}
}
cout << ans << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int t=1;//cin >> t;
while(t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
2 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
3 ms |
600 KB |
Output is correct |
10 |
Correct |
4 ms |
344 KB |
Output is correct |
11 |
Correct |
4 ms |
344 KB |
Output is correct |
12 |
Correct |
4 ms |
348 KB |
Output is correct |
13 |
Correct |
3 ms |
344 KB |
Output is correct |
14 |
Correct |
4 ms |
344 KB |
Output is correct |
15 |
Correct |
3 ms |
344 KB |
Output is correct |
16 |
Correct |
4 ms |
344 KB |
Output is correct |
17 |
Correct |
10 ms |
3672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1230 ms |
8144 KB |
Output is correct |
2 |
Correct |
1603 ms |
9416 KB |
Output is correct |
3 |
Correct |
914 ms |
6868 KB |
Output is correct |
4 |
Correct |
1701 ms |
9784 KB |
Output is correct |
5 |
Correct |
1744 ms |
9804 KB |
Output is correct |
6 |
Correct |
1827 ms |
10184 KB |
Output is correct |
7 |
Correct |
1811 ms |
10192 KB |
Output is correct |
8 |
Correct |
1816 ms |
10184 KB |
Output is correct |
9 |
Correct |
1835 ms |
10192 KB |
Output is correct |
10 |
Correct |
1810 ms |
10324 KB |
Output is correct |
11 |
Correct |
988 ms |
10192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
2 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
3 ms |
600 KB |
Output is correct |
10 |
Correct |
4 ms |
344 KB |
Output is correct |
11 |
Correct |
4 ms |
344 KB |
Output is correct |
12 |
Correct |
4 ms |
348 KB |
Output is correct |
13 |
Correct |
3 ms |
344 KB |
Output is correct |
14 |
Correct |
4 ms |
344 KB |
Output is correct |
15 |
Correct |
3 ms |
344 KB |
Output is correct |
16 |
Correct |
4 ms |
344 KB |
Output is correct |
17 |
Correct |
10 ms |
3672 KB |
Output is correct |
18 |
Correct |
1230 ms |
8144 KB |
Output is correct |
19 |
Correct |
1603 ms |
9416 KB |
Output is correct |
20 |
Correct |
914 ms |
6868 KB |
Output is correct |
21 |
Correct |
1701 ms |
9784 KB |
Output is correct |
22 |
Correct |
1744 ms |
9804 KB |
Output is correct |
23 |
Correct |
1827 ms |
10184 KB |
Output is correct |
24 |
Correct |
1811 ms |
10192 KB |
Output is correct |
25 |
Correct |
1816 ms |
10184 KB |
Output is correct |
26 |
Correct |
1835 ms |
10192 KB |
Output is correct |
27 |
Correct |
1810 ms |
10324 KB |
Output is correct |
28 |
Correct |
988 ms |
10192 KB |
Output is correct |
29 |
Correct |
1000 ms |
11720 KB |
Output is correct |
30 |
Correct |
87 ms |
2008 KB |
Output is correct |
31 |
Correct |
191 ms |
3276 KB |
Output is correct |
32 |
Correct |
544 ms |
7620 KB |
Output is correct |
33 |
Correct |
228 ms |
3524 KB |
Output is correct |
34 |
Correct |
248 ms |
3788 KB |
Output is correct |
35 |
Correct |
149 ms |
2520 KB |
Output is correct |
36 |
Correct |
74 ms |
1752 KB |
Output is correct |
37 |
Correct |
93 ms |
2008 KB |
Output is correct |
38 |
Correct |
422 ms |
10224 KB |
Output is correct |
39 |
Correct |
409 ms |
10184 KB |
Output is correct |
40 |
Correct |
401 ms |
10192 KB |
Output is correct |
41 |
Correct |
399 ms |
10696 KB |
Output is correct |
42 |
Correct |
409 ms |
10196 KB |
Output is correct |
43 |
Correct |
419 ms |
11720 KB |
Output is correct |
44 |
Correct |
405 ms |
11720 KB |
Output is correct |
45 |
Correct |
403 ms |
11720 KB |
Output is correct |
46 |
Correct |
441 ms |
11720 KB |
Output is correct |
47 |
Correct |
454 ms |
12092 KB |
Output is correct |
48 |
Correct |
1515 ms |
10440 KB |
Output is correct |
49 |
Correct |
1519 ms |
10440 KB |
Output is correct |
50 |
Correct |
816 ms |
10436 KB |
Output is correct |
51 |
Correct |
819 ms |
10440 KB |
Output is correct |
52 |
Correct |
314 ms |
7376 KB |
Output is correct |
53 |
Correct |
2447 ms |
10696 KB |
Output is correct |
54 |
Correct |
1517 ms |
10440 KB |
Output is correct |