Submission #217632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
217632	2020-03-30T11:24:38 Z	dimash241	The grade (info1cup18_thegrade)	C++17	100 / 100	58 ms	14072 KB

thegrade

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

//# include <ext/pb_ds/assoc_container.hpp>
//# include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;
 
//template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int mult (int a, int b) {
	return a *(ll)b%mod;
}
int cnt[mxn];
int fac[mxn];
int inv[mxn];
int ifac[mxn];


int main () {
	SpeedForce;
	cin >> m >> n;
	ll sum = n;
	int cdiv = 1;
	int siz = 0;
	fac[0] = ifac[0] = 1;
	fac[1] = ifac[1] = 1;
	inv[1] = inv[0] = 1;
	for (int i = 2; i < mxn; ++i) {
		inv[i] = mult((mod - mod/i), inv[mod%i]);
		fac[i] = mult(fac[i-1], i);
		ifac[i] = mult(ifac[i-1], inv[i]);
	}

	for (int i = 1; i <= m; ++i) {
		int op, x;
		cin >> op >> x;
		if (op == 0) {
			++siz;
			sum -= x;
			cdiv = mult(cdiv, inv[++cnt[x]]);
		} else {
			--siz;
			sum += x;
			cdiv = mult(cdiv, cnt[x]--);
		}


		if (sum >= 0) cout << mult(cdiv, mult(fac[siz + sum], ifac[sum]));
		else cout << -1;
		cout << '\n';
	}

	return Accepted;
}

// B...a

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	12024 KB	Output is correct
2	Correct	26 ms	12024 KB	Output is correct
3	Correct	26 ms	12024 KB	Output is correct
4	Correct	28 ms	12024 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	12152 KB	Output is correct
2	Correct	50 ms	13176 KB	Output is correct
3	Correct	51 ms	13688 KB	Output is correct
4	Correct	49 ms	13432 KB	Output is correct
5	Correct	50 ms	13176 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	12160 KB	Output is correct
2	Correct	53 ms	13560 KB	Output is correct
3	Correct	53 ms	13560 KB	Output is correct
4	Correct	53 ms	13560 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	12024 KB	Output is correct
2	Correct	26 ms	12024 KB	Output is correct
3	Correct	26 ms	12024 KB	Output is correct
4	Correct	28 ms	12024 KB	Output is correct
5	Correct	27 ms	12152 KB	Output is correct
6	Correct	50 ms	13176 KB	Output is correct
7	Correct	51 ms	13688 KB	Output is correct
8	Correct	49 ms	13432 KB	Output is correct
9	Correct	50 ms	13176 KB	Output is correct
10	Correct	27 ms	12160 KB	Output is correct
11	Correct	53 ms	13560 KB	Output is correct
12	Correct	53 ms	13560 KB	Output is correct
13	Correct	53 ms	13560 KB	Output is correct
14	Correct	27 ms	12160 KB	Output is correct
15	Correct	52 ms	13432 KB	Output is correct
16	Correct	49 ms	13560 KB	Output is correct
17	Correct	54 ms	13432 KB	Output is correct

Subtask #5

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	12152 KB	Output is correct
2	Correct	50 ms	13176 KB	Output is correct
3	Correct	51 ms	13688 KB	Output is correct
4	Correct	49 ms	13432 KB	Output is correct
5	Correct	50 ms	13176 KB	Output is correct
6	Correct	57 ms	13560 KB	Output is correct
7	Correct	49 ms	13560 KB	Output is correct
8	Correct	52 ms	13688 KB	Output is correct
9	Correct	49 ms	13560 KB	Output is correct

Subtask #6

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	12160 KB	Output is correct
2	Correct	53 ms	13560 KB	Output is correct
3	Correct	53 ms	13560 KB	Output is correct
4	Correct	53 ms	13560 KB	Output is correct
5	Correct	54 ms	13816 KB	Output is correct
6	Correct	55 ms	13816 KB	Output is correct
7	Correct	58 ms	14072 KB	Output is correct
8	Correct	55 ms	13816 KB	Output is correct

Subtask #7

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	12024 KB	Output is correct
2	Correct	26 ms	12024 KB	Output is correct
3	Correct	26 ms	12024 KB	Output is correct
4	Correct	28 ms	12024 KB	Output is correct
5	Correct	27 ms	12152 KB	Output is correct
6	Correct	50 ms	13176 KB	Output is correct
7	Correct	51 ms	13688 KB	Output is correct
8	Correct	49 ms	13432 KB	Output is correct
9	Correct	50 ms	13176 KB	Output is correct
10	Correct	27 ms	12160 KB	Output is correct
11	Correct	53 ms	13560 KB	Output is correct
12	Correct	53 ms	13560 KB	Output is correct
13	Correct	53 ms	13560 KB	Output is correct
14	Correct	27 ms	12160 KB	Output is correct
15	Correct	52 ms	13432 KB	Output is correct
16	Correct	49 ms	13560 KB	Output is correct
17	Correct	54 ms	13432 KB	Output is correct
18	Correct	57 ms	13560 KB	Output is correct
19	Correct	49 ms	13560 KB	Output is correct
20	Correct	52 ms	13688 KB	Output is correct
21	Correct	49 ms	13560 KB	Output is correct
22	Correct	54 ms	13816 KB	Output is correct
23	Correct	55 ms	13816 KB	Output is correct
24	Correct	58 ms	14072 KB	Output is correct
25	Correct	55 ms	13816 KB	Output is correct
26	Correct	50 ms	13560 KB	Output is correct
27	Correct	49 ms	13560 KB	Output is correct
28	Correct	49 ms	13560 KB	Output is correct
29	Correct	50 ms	13688 KB	Output is correct
30	Correct	51 ms	13560 KB	Output is correct