Submission #502921

#	Time	Username	Problem	Language	Result	Execution time	Memory
502921		MilosMilutinovic	Diversity (CEOI21_diversity)	C++14	0 / 100	4 ms	7384 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=301000;
int n,q,a[N],blk,cc[N],cnt[N];
vector<PII> hv[N];

struct query {
	int l,r,i;
	bool operator < (const query qq) const {
		if (r/blk==qq.r/blk) return l<qq.l;
		else return r/blk<qq.r/blk;		
	}
}Q[N];

set<int> s;

void Add(int c) {
	cc[cnt[c]]--;
	if (!cc[cnt[c]]) s.erase(s.find(cnt[c]));
	cnt[c]++;
	cc[cnt[c]]++;
	if (cc[cnt[c]]==1) s.insert(cnt[c]);
}

void Rem(int c) {
	cc[cnt[c]]--;
	if (!cc[cnt[c]]) s.erase(s.find(cnt[c]));
	cnt[c]--;
	cc[cnt[c]]++;
	if (cc[cnt[c]]==1) s.insert(cnt[c]);
}

int main() {
	scanf("%d%d",&n,&q);
	blk=int(sqrt(n));
	rep(i,1,n+1) scanf("%d",a+i);
	rep(i,1,q+1) {
		scanf("%d%d",&Q[i].l,&Q[i].r);
		Q[i].i=i;
	}
	sort(Q+1,Q+q+1);
	int L=0,R=-1;
	rep(i,1,q+1) {
		while (L<Q[i].l) Rem(a[L++]);
		while (L>Q[i].l) Add(a[--L]);
		while (R<Q[i].r) Add(a[++R]);
		while (R>Q[i].r) Rem(a[R--]);
		for (auto pp:s) hv[Q[i].i].pb({pp,cc[pp]});
	}
}

Compilation message (stderr)

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:55:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  rep(i,1,n+1) scanf("%d",a+i);
      |               ~~~~~^~~~~~~~~~
diversity.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d%d",&Q[i].l,&Q[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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