Submission #1084178

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1084178	2024-09-05 14:20:27	onlk97	Diversity (CEOI21_diversity)	C++14	64 / 100	7028 ms	4876 KiB

diversity

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int L,R;
int a[300010];
long long freq[300010],freq2[300010];
bitset <300010> have;
long long calcans(){
    long long ans=0,lps=0,rps=0,s=R-L+1;
    for (int i=have._Find_first(); i<300010; i=have._Find_next(i)){
        long long cntl,cntr;
        int f;
        if (lps<=rps){
            f=min(freq2[i],(rps-lps)/i+1);
            cntl=f+(freq2[i]-f)/2,cntr=(freq2[i]-f+1)/2;
        } else {
            f=min(freq2[i],(lps-rps)/i+1);
            cntl=(freq2[i]-f+1)/2,cntr=f+(freq2[i]-f)/2;
        }
        ans+=cntl*lps*lps+cntl*(cntl+1)*lps*i+cntl*(cntl+1)/2*(2*cntl+1)/3*i*i;
        ans-=s*(lps+i+lps+i*cntl)*cntl/2;
        lps+=cntl*i;
        long long t=s-rps;
        ans+=cntr*t*t-cntr*(cntr-1)*t*i+(cntr)*(cntr-1)/2*(2*cntr-1)/3*i*i;
        ans-=s*(t+t-(cntr-1)*i)*cntr/2;
        rps+=cntr*i;
    }
    return s*(s+1)/2-ans;
}
const int BLOCK=850;
bool cmp(pair <pair <int,int>,int> a,pair <pair <int,int>,int> b){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36