oj.uz

Submission #90862

# Submission time Handle Problem Language Result Execution time Memory
90862 2018-12-25T03:23:14 Z jasony123123 Žarulje (COI15_zarulje) C++11
100 / 100
 212 ms 38132 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
/****************************************************************/

ll pow(ll a, ll p) {
	ll ret = 1LL;
	while (p) {
		if (p & 1LL)
			ret *= a;
		a *= a;
		ret %= MOD;
		a %= MOD;
		p >>= 1;
	}
	return ret;
}

ll inv(ll x) { // this give the modular inverse, albeit slowly
	x %= MOD;
	return pow(x, MOD - 2LL);
}

const int MAXN = 200099;
ll fact[MAXN], ifact[MAXN];

void precomp(int n) {
	fact[0] = 1;
	FORE(i, 1, n) fact[i] = ((ll)i*fact[i - 1]) % MOD;
	FORE(i, 0, n) ifact[i] = inv(fact[i]);
}
ll choose(int n, int r) {
	assert(n >= r);
	return (((fact[n] * ifact[n - r]) % MOD) * ifact[r]) % MOD;
}
ll invchoose(int n, int r) {
	assert(n >= r);
	return (((fact[r] * fact[n - r]) % MOD) * ifact[n]) % MOD;
}

int N, Q;
int A[MAXN];
int lcnt[MAXN], rcnt[MAXN];
v<pii> changes[MAXN];
ll allans[MAXN];

void initR() {
	// precompute right segments
	stack<int> st;
	RFORE(i, N - 1, 1) {
		while (!st.empty() && A[i] < st.top()) {
			changes[i].push_back({ st.top(), -1 });
			rcnt[st.top()]--;
			st.pop();
		}
		changes[i].push_back({ A[i], 1 });
		st.push(A[i]);
		rcnt[A[i]]++;
	}
}
int main() {
	io();
	cin >> N >> Q;
	FOR(i, 0, N) cin >> A[i];
	precomp(N);
	initR();

	allans[0] = 1;
	ll ans = 1;
	stack<int> stac;
	FOR(i, 1, N) {
		v<pii> lchanges;
		set<int> changedNums;

		// add [i-1] into left
		while (!stac.empty() && stac.top() > A[i - 1]) {
			lchanges.push_back({ stac.top(), -1 });
			changedNums.insert(stac.top());
			stac.pop();
		}
		lchanges.push_back({ A[i - 1], 1 });
		changedNums.insert(A[i - 1]);
		stac.push(A[i - 1]);

		// remove [i] from right
		for (pii &c : changes[i]) changedNums.insert(c.first);

		for (int x : changedNums) {
			ans *= invchoose(lcnt[x] + rcnt[x], lcnt[x]);
			ans %= MOD;
		}

		for (pii &c : lchanges) {
			lcnt[c.first] += c.second;
		}
		for (pii &c : changes[i]) {
			rcnt[c.first] -= c.second;
		}

		for (int x : changedNums) {
			ans *= choose(lcnt[x] + rcnt[x], lcnt[x]);
			ans %= MOD;
		}
		allans[i] = ans;
	}


	FOR(i, 0, Q) {
		int p;
		cin >> p;
		p--;
		cout << allans[p] << "\n";
	}

	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5244 KB Output is correct
3 Correct 7 ms 5308 KB Output is correct
4 Correct 7 ms 5488 KB Output is correct
5 Correct 7 ms 5604 KB Output is correct
6 Correct 7 ms 5604 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 11992 KB Output is correct
2 Correct 138 ms 18724 KB Output is correct
3 Correct 148 ms 19316 KB Output is correct
4 Correct 149 ms 20188 KB Output is correct
5 Correct 153 ms 21244 KB Output is correct
6 Correct 181 ms 23016 KB Output is correct
7 Correct 176 ms 25112 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5244 KB Output is correct
3 Correct 7 ms 5308 KB Output is correct
4 Correct 7 ms 5488 KB Output is correct
5 Correct 7 ms 5604 KB Output is correct
6 Correct 7 ms 5604 KB Output is correct
7 Correct 77 ms 11992 KB Output is correct
8 Correct 138 ms 18724 KB Output is correct
9 Correct 148 ms 19316 KB Output is correct
10 Correct 149 ms 20188 KB Output is correct
11 Correct 153 ms 21244 KB Output is correct
12 Correct 181 ms 23016 KB Output is correct
13 Correct 176 ms 25112 KB Output is correct
14 Correct 15 ms 25112 KB Output is correct
15 Correct 96 ms 25112 KB Output is correct
16 Correct 175 ms 28248 KB Output is correct
17 Correct 170 ms 28512 KB Output is correct
18 Correct 183 ms 31392 KB Output is correct
19 Correct 175 ms 31748 KB Output is correct
20 Correct 212 ms 34744 KB Output is correct
21 Correct 206 ms 38132 KB Output is correct