oj.uz

Submission #576386

# Submission time Handle Problem Language Result Execution time Memory
576386 2022-06-13T05:22:55 Z temporary_juggernaut Diversity (CEOI21_diversity) C++14
4 / 100
 7000 ms 2320 KB 
#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];
int cnt[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]*(r-l+1);
	lazy[v]=0;
}
void update(int v,int l,int r,int ql,int qr){
	push(v,l,r);
	if(qr<l||r<ql)return;
	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);
}*/
void update(int v,int l,int r,int ql,int qr){
	for(int i=ql;i<=qr;i++)tree[i]++;
}
ll get(int v,int l,int r,int ql,int qr){
	ll sum=0;
	for(int i=ql;i<=qr;i++)sum+=tree[i];
	return sum;
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	assert(q==1);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		cnt[x]++;
	}
	vector<int>vec;
	for(int i=1;i<=300000;i++)if(cnt[i])vec.push_back(cnt[i]);
	sort(vec.begin(),vec.end());
	int idx=1;
	int ide=n;
	int val=1;
	for(int to:vec){
		if(val&1)
			while(to--)a[idx++]=val;
		else
			while(to--)a[ide--]=val;
		val++;
	}
	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:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
diversity.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 25 ms 428 KB Output is correct
4 Correct 2468 ms 1464 KB Output is correct
5 Execution timed out 7084 ms 2320 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 25 ms 428 KB Output is correct
4 Correct 2468 ms 1464 KB Output is correct
5 Execution timed out 7084 ms 2320 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 25 ms 428 KB Output is correct
4 Correct 2468 ms 1464 KB Output is correct
5 Execution timed out 7084 ms 2320 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 25 ms 428 KB Output is correct
14 Correct 2468 ms 1464 KB Output is correct
15 Execution timed out 7084 ms 2320 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 25 ms 428 KB Output is correct
14 Correct 2468 ms 1464 KB Output is correct
15 Execution timed out 7084 ms 2320 KB Time limit exceeded
16 Halted 0 ms 0 KB -