oj.uz

Submission #372452

# Submission time Handle Problem Language Result Execution time Memory
372452 2021-02-28T08:39:34 Z ngpin04 Žarulje (COI15_zarulje) C++14
100 / 100
 369 ms 17644 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

vector <int> val[N];
vector <int> f;
vector <int> g;

int cntl[N];
int cntr[N];
int ans[N];
int fac[2 * N];
int inv[2 * N];
int a[N];
int n,m,cur = 1;

int binpow(int n, int k) {
	int res = 1;

	for (; k; k >>= 1, n = (long long) n * n % mod)
		if (k & 1)
			res = (long long) res * n % mod;
	return res;
}

int calc(int i, int j) {
	return (long long) fac[i + j] * inv[i] % mod * inv[j] % mod;
}

void add(int cnt[], int pos, int val) {
	cur = (long long) cur * binpow(calc(cntl[pos], cntr[pos]), mod - 2) % mod; //assert(cur);
	cnt[pos] += val;
	cur = (long long) cur * calc(cntl[pos], cntr[pos]) % mod; //assert(cur);
}

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		cin >> a[i];	
	
	fac[0] = 1;
	for (int i = 1; i <= 2 * n; i++)
		fac[i] = (long long) fac[i - 1] * i % mod;

	inv[2 * n] = binpow(fac[2 * n], mod - 2);

	for (int i = 2 * n - 1; i >= 0; i--)
		inv[i] = (long long) inv[i + 1] * (i + 1) % mod;

	// for (int i = 0; i <= 2 * n; i++)
	// 	cout << fac[i] << " " << inv[i] << endl;
	// return 0;


	for (int i = n; i >= 1; i--) {
		while (g.size() && a[i] < a[g.back()]) {
			val[i].push_back(g.back());
			add(cntr, a[g.back()], -1);
			g.pop_back();
		}

		g.push_back(i);
		add(cntr, a[i], 1);
	}

	for (int i = 1; i <= n; i++) {
		add(cntr, a[i], -1);
		g.pop_back();

		while (val[i].size()) {
			g.push_back(val[i].back());
			add(cntr, a[val[i].back()], 1);
			val[i].pop_back();
		}

		// cout << "pos " << i << ": " << cur << endl;

		// for (int x : f)
		// 	cout << x << " ";
		// cout << endl;

		// for (int x : g)
		// 	cout << x << " ";
		// cout << endl;

		ans[i] = cur;

		while (f.size() && a[i] < a[f.back()]) {
			add(cntl, a[f.back()], -1);
			f.pop_back();
		}

		f.push_back(i);
		add(cntl, a[i], 1);
	}

	while (m--) {
		int pos;
		cin >> pos;
		cout << ans[pos] << "\n";
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Correct 7 ms 5228 KB Output is correct
4 Correct 7 ms 5100 KB Output is correct
5 Correct 7 ms 5100 KB Output is correct
6 Correct 7 ms 5228 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 9068 KB Output is correct
2 Correct 289 ms 13020 KB Output is correct
3 Correct 299 ms 13676 KB Output is correct
4 Correct 313 ms 13932 KB Output is correct
5 Correct 307 ms 14112 KB Output is correct
6 Correct 310 ms 15084 KB Output is correct
7 Correct 324 ms 15852 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Correct 7 ms 5228 KB Output is correct
4 Correct 7 ms 5100 KB Output is correct
5 Correct 7 ms 5100 KB Output is correct
6 Correct 7 ms 5228 KB Output is correct
7 Correct 150 ms 9068 KB Output is correct
8 Correct 289 ms 13020 KB Output is correct
9 Correct 299 ms 13676 KB Output is correct
10 Correct 313 ms 13932 KB Output is correct
11 Correct 307 ms 14112 KB Output is correct
12 Correct 310 ms 15084 KB Output is correct
13 Correct 324 ms 15852 KB Output is correct
14 Correct 22 ms 5612 KB Output is correct
15 Correct 186 ms 10928 KB Output is correct
16 Correct 323 ms 16580 KB Output is correct
17 Correct 319 ms 15212 KB Output is correct
18 Correct 340 ms 17004 KB Output is correct
19 Correct 323 ms 15212 KB Output is correct
20 Correct 365 ms 16556 KB Output is correct
21 Correct 369 ms 17644 KB Output is correct