Submission #363929

#	Time	Username	Problem	Language	Result	Execution time	Memory
363929		ogibogi2004	The grade (info1cup18_thegrade)	C++14	100 / 100	410 ms	10476 KiB

thegrade

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e6+6;
const ll mod=1e9+7;
ll fastpow(ll x,ll p)
{
	if(p==0)return 1;
	ll t=fastpow(x,p/2);
	t*=t;t%=mod;
	if(p%2==1)t*=x;
	t%=mod;return t;
}
ll inv(ll x)
{
	return fastpow(x,mod-2);
}
ll fact[MAXN];
ll cnt[MAXN],bigX=1,cntall,sum;
ll comb(ll n,ll k)
{
	if(k>n)return 0;
	ll ret=fact[n];
	ret*=inv(fact[k]);
	ret%=mod;
	ret*=inv(fact[n-k]);
	ret%=mod;
	return ret;
}
void add(ll x)
{
	cntall++;sum+=x;
	bigX*=cntall;
	bigX%=mod;
	cnt[x]++;
	bigX*=inv(cnt[x]);
	bigX%=mod;
}
void remove(ll x)
{
	bigX*=inv(cntall);
	bigX%=mod;sum-=x;
	cntall--;
	bigX*=cnt[x];
	bigX%=mod;
	cnt[x]--;
}
ll q,p;
ll calc()
{
	ll ret=1;
	ret=comb(cntall+p-sum,p-sum);
	ret*=bigX;
	ret%=mod;
	if(ret==0)return -1;
	return ret;
}
void precompute()
{
	fact[0]=1;
	for(ll i=1;i<MAXN;i++)
	{
		fact[i]=fact[i-1]*i;
		fact[i]%=mod;
	}
}
int main()
{
	precompute();
	cin>>q>>p;
	for(int i=0;i<q;i++)
	{
		int type,x;
		cin>>type>>x;
		if(type==1)remove(x);
		else add(x);
		cout<<calc()<<endl;
	}
return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20