Submission #915841

#	Time	Username	Problem	Language	Result	Execution time	Memory
915841		andrei_iorgulescu	The grade (info1cup18_thegrade)	C++14	100 / 100	103 ms	7252 KiB

thegrade

#include <bits/stdc++.h>

using namespace std;

#define int long long

int modulo = 1e9 + 7;
int fact[200005],invfact[200005];
int n,suma,q,p,rep = 1;
int fr[1000005];

int C(int x,int y)
{
    return fact[x] * invfact[y] % modulo * invfact[x - y] % modulo;
}

int lgpow(int x,int y)
{
    int z = 1;
    while (y != 0)
    {
        if (y % 2 == 1)
            z = z * x % modulo;
        x = x * x % modulo;
        y /= 2;
    }
    return z;
}

int sb(int x,int y)
{
    return C(x + y - 1,y - 1);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    fact[0] = invfact[0] = 1;
    for (int i = 1; i <= 200000; i++)
    {
        fact[i] = fact[i - 1] * i % modulo;
        invfact[i] = lgpow(fact[i],modulo - 2);
    }
    cin >> q >> p;
    for (int i = 1; i <= q; i++)
    {
        int x,y;
        cin >> x >> y;
        if (x == 0)
        {
            rep *= fact[fr[y]];
            rep %= modulo;
            fr[y]++;
            n++;
            suma += y;
            rep *= invfact[fr[y]];
            rep %= modulo;
        }
        else
        {
            rep *= fact[fr[y]];
            rep %= modulo;
            fr[y]--;
            n--;
            suma -= y;
            rep *= invfact[fr[y]];
            rep %= modulo;
        }
        if (suma > p)
            cout << -1 << '\n';
        else
            cout << fact[n] * sb(p - suma,n + 1) % modulo * rep % modulo << '\n';
    }
    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