#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...)printf(args)
#else
#define printl(args...)((void)0)
#endif
int a[300005];
ll tree[4*300005];
ll lazy[4*300005];
void push(int v,int l,int r){
if(l!=r){
lazy[v<<1]+=lazy[v];
lazy[v<<1|1]+=lazy[v];
}
tree[v]+=lazy[v]*1ll*(r-l+1);
lazy[v]=0;
}
void update(int v,int l,int r,int ql,int qr){
if(qr<l||r<ql)return;
push(v,l,r);
if(ql<=l&&r<=qr){
lazy[v]++;
push(v,l,r);
return;
}
int mid=(l+r)>>1;
update(v<<1,l,mid,ql,qr);
update(v<<1|1,mid+1,r,ql,qr);
tree[v]=tree[v<<1]+tree[v<<1|1];
}
ll get(int v,int l,int r,int ql,int qr){
if(qr<l||r<ql)return 0ll;
push(v,l,r);
if(ql<=l&&r<=qr)return tree[v];
int mid=(l+r)>>1;
return get(v<<1,l,mid,ql,qr)+get(v<<1|1,mid+1,r,ql,qr);
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
assert(q==1);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
ll sum=0;
for(int i=1;i<=n;i++){
update(1,1,n,(a[i]==a[i-1]?i:1),i);
sum+=get(1,1,n,1,i);
}
cout<<sum;
}
Compilation message
diversity.cpp: In function 'int main()':
diversity.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
diversity.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
232 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
232 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
232 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
