oj.uz

Submission #283663

# Submission time Handle Problem Language Result Execution time Memory
283663 2020-08-26T04:55:13 Z 임성재(#5753) Žarulje (COI15_zarulje) C++17
22 / 100
 43 ms 13560 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const ll inf = 1e9 + 7;

ll inv(ll a) {
	ll b = inf - 2;
	ll ret = 1;

	while(b) {
		if(b & 1) ret *= a;
		a *= a;
		b >>= 1;
		ret %= inf;
		a %= inf;
	}

	return ret;
}

int n, k;
int a[200010];
ll f[200010];
ll in[200010];
vector<int> l, r;
vector<int> er[100010];
ll ans[200010];
int cnt[2][200010];
ll p[200010];

int main() {
	fast;

	cin >> n >> k;

	f[0] = 1;
	for(int i=1; i<=n; i++)
		f[i] = f[i-1] * i % inf;

	in[n] = inv(f[n]);

	for(int i=n; i>=1; i--) {
		in[i-1] = in[i] * i % inf;
	}

	for(int i=1; i<=n; i++) {
		cin >> a[i];
	}

	for(int i = n; i >= 1; i--) {
		while(r.size() && r.back()> a[i]) cnt[1][r.back()]--, er[i].eb(r.back()), r.pop_back();
		r.eb(a[i]);
		cnt[1][a[i]]++;
	}

	ll ans = 1;

	for(int i=1; i<=n; i++) {
		ans = ans * in[cnt[0][r.back()] + cnt[1][r.back()]] % inf * f[cnt[0][r.back()]] % inf * f[cnt[1][r.back()]] % inf;
		cnt[1][r.back()]--;
		ans = ans * f[cnt[0][r.back()] + cnt[1][r.back()]] % inf * in[cnt[0][r.back()]] % inf * in[cnt[1][r.back()]] % inf;
		
		r.pop_back();

		reverse(all(er[i]));
		for(auto j : er[i]) {
			ans = ans * in[cnt[0][j] + cnt[1][j]] % inf * f[cnt[0][j]] % inf * f[cnt[1][j]] % inf;
			cnt[1][j]++;
			ans = ans * f[cnt[0][j] + cnt[1][j]] % inf * in[cnt[0][j]] % inf * in[cnt[1][j]] % inf;

			r.eb(j);
		}

		p[i] = ans;
		
		while(l.size() && l.back() > a[i]) {
			ans = ans * in[cnt[0][l.back()] + cnt[1][l.back()]] % inf * f[cnt[0][l.back()]] % inf * f[cnt[1][l.back()]] % inf;
			cnt[0][l.back()]--;
			ans = ans * f[cnt[0][l.back()] + cnt[1][l.back()]] % inf * in[cnt[0][l.back()]] % inf * in[cnt[1][l.back()]] % inf;

			l.pop_back();
		}

		l.eb(a[i]);
		
		ans = ans * in[cnt[0][a[i]] + cnt[1][a[i]]] % inf * f[cnt[0][a[i]]] % inf * f[cnt[1][a[i]]] % inf;
		cnt[0][a[i]]++;
		ans = ans * f[cnt[0][a[i]] + cnt[1][a[i]]] % inf * in[cnt[0][a[i]]] % inf * in[cnt[1][a[i]]] % inf;
	}

	while(k--) {
		int x;
		cin >> x;

		cout << p[x] << "\n";
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 3 ms 2944 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7424 KB Output is correct
2 Runtime error 43 ms 13560 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 3 ms 2944 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 35 ms 7424 KB Output is correct
8 Runtime error 43 ms 13560 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -