Submission #446719

#	Time	Username	Problem	Language	Result	Execution time	Memory
446719		oubwoeiniw	Matching (CEOI11_mat)	C++17	0 / 100	2069 ms	63444 KiB

mat

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;


#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const ll MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;
const ll p = 2;

inline ll poww(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}

	return ans;
}

ll sg[MAXN << 2], lz[MAXN << 2], H[MAXN], n, m, t_hsh, hsh, 
   p_pow[MAXN], B[MAXN], inv, ind[MAXN];
ordered_set st;

void Push(int v) {
	sg[v] = sg[v] * lz[v] % MOD;
	if ((v << 1 | 1) < (MAXN << 2)) {
		lz[v << 1] = (lz[v << 1] * lz[v]) % MOD;
		lz[v << 1 | 1] = (lz[v << 1 | 1] * lz[v]) % MOD;
	}

	lz[v] = 1;
}

ll Query(int QL, int QR = MAXN - 1, int L = 1, int R = MAXN - 1, int v = 1) {
	Push(v);
	if (QL > QR) return 0;
	if (QL == L && QR == R) return sg[v];

	int mid = (L + R) >> 1;
	return (Query(QL, min(QR, mid), L, mid, v << 1) + 
			Query(max(QL, mid + 1), QR, mid + 1, R, v << 1 | 1)) % MOD;
}

void Reset(int ind, ll val, int L = 1, int R = MAXN - 1, int v = 1) {
	Push(v);
	if (L == R) {
		sg[v] = val;
		return;
	}	

	int mid = (L + R) >> 1;
	if (ind <= mid) Reset(ind, val, L, mid, v << 1);
	else Reset(ind, val, mid + 1, R, v << 1 | 1);
	Push(v << 1);
	Push(v << 1 | 1);
	sg[v] = (sg[v << 1] + sg[v << 1 | 1]) % MOD;
}

inline void Divide() {
	lz[1] = lz[1] * inv % MOD;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	p_pow[0] = 1;
	for (int i = 1; i < MAXN; i++) 
		p_pow[i] = p_pow[i - 1] * p % MOD;
	for (int i = 1; i < (MAXN << 2); i++)
		lz[i] = 1;
	inv = poww(p, MOD - 2);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		ll x;
		cin >> x;
		ind[x] = i;
	}

	for (int i = 0; i < n; i++) {
		t_hsh = (t_hsh + p_pow[i] * (ind[i + 1] + 1)) % MOD;
	}

	int ans = 0;
	for (int i = 0; i < m; i++) {
		cin >> B[i];
		if (i >= n) {
			ll ind = st.order_of_key(B[i - n]) + 1;
			hsh = (hsh - ind + MOD) % MOD; // remove first element
			hsh = hsh * inv % MOD; // div by p		
			Divide(); // div seg by p
			hsh = (hsh - Query(B[i - n] + 1) + MOD) % MOD; // dec ind
			st.erase(st.lower_bound(B[i - n]));
			Reset(B[i - n], 0);
		}


		ll pw = p_pow[min(1ll * i, n - 1)], ind = st.order_of_key(B[i]) + 1;
		st.insert(B[i]);
		hsh = (hsh + Query(B[i])) % MOD; // inc ind
		hsh = (hsh + pw * ind) % MOD; // add last element
		Reset(B[i], pw);
		
		if (i >= n - 1 && hsh == t_hsh) {
			ans++;
		}

	}	

	cout << ans << endl;
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10