Submission #446716

#	Time	Username	Problem	Language	Result	Execution time	Memory
446716		oubwoeiniw	Matching (CEOI11_mat)	C++17	0 / 100	2092 ms	59540 KiB

mat

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 1e6 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod[2] = {1000000007, 998244353};
const int base = 257;

int n, m, a[xn], pw[2][xn], inv[2][xn], fen[xn], ans, lazy[xn << 2];
pii seg[xn << 2], hsh, b[xn], sum;

void mofen(int pos, int val){
	for (pos += 5; pos < xn; pos += pos & - pos)
		fen[pos] += val;
}
int gefen(int pos){
	int res = 0;
	for (pos += 5; 0 < pos; pos -= pos & - pos)
		res += fen[pos];
	return res;
}
void shift(int id, int l, int r){
	if (!lazy[id])
		return;
	if (0 < lazy[id]){
		seg[id].A = 1ll * seg[id].A * pw[0][lazy[id]] % mod[0];
		seg[id].B = 1ll * seg[id].B * pw[1][lazy[id]] % mod[1];
	}
	else{
		seg[id].A = 1ll * seg[id].A * inv[0][- lazy[id]] % mod[0];
		seg[id].B = 1ll * seg[id].B * inv[1][- lazy[id]] % mod[1];
	}
	if (1 < r - l){
		lazy[lc] += lazy[id];
		lazy[rc] += lazy[id];
	}
	lazy[id] = 0;
}
void update(int id, int l, int r, int ql, int qr, int val){
	shift(id, l, r);
	if (qr <= l || r <= ql || qr <= ql)
		return;
	if (ql <= l && r <= qr){
		lazy[id] += val;
		shift(id, l, r);
		return;
	}
	int mid = l + r >> 1;
	update(lc, l, mid, ql, qr, val);
	update(rc, mid, r, ql, qr, val);
	seg[id].A = (seg[lc].A + seg[rc].A) % mod[0];
	seg[id].B = (seg[lc].B + seg[rc].B) % mod[1];
}
void modify(int id, int l, int r, int pos, pii val){
	shift(id, l, r);
	if (r - l == 1){
		seg[id] = val;
		return;
	}
	int mid = l + r >> 1;
	if (pos < mid)
		modify(lc, l, mid, pos, val);
	else
		modify(rc, mid, r, pos, val);
	shift(lc, l, mid), shift(rc, mid, r);
	seg[id].A = (seg[lc].A + seg[rc].A) % mod[0];
	seg[id].B = (seg[lc].B + seg[rc].B) % mod[1];
}
void add(int x, int y){
	int y1 = 1ll * y * pw[0][gefen(x)] % mod[0];
	int y2 = 1ll * y * pw[1][gefen(x)] % mod[1];
	modify(1, 1, m + 1, x, {y1, y2});
	update(1, 1, m + 1, x + 1, m + 1, 1);
	mofen(x, 1);
}
void rem(int x, int y){
	modify(1, 1, m + 1, x, {0, 0});
	update(1, 1, m + 1, x + 1, m + 1, - 1);
	mofen(x, - 1);
}

int main(){
	fast_io;

	for (int i = 0; i < 2; ++ i){
		pw[i][0] = inv[i][0] = 1;
		pw[i][1] = base;
		inv[i][1] = power(base, mod[i] - 2, mod[i]);
		for (int j = 2; j < xn; ++ j){
			pw[i][j] = 1ll * pw[i][j - 1] * pw[i][1] % mod[i];
			inv[i][j] = 1ll * inv[i][j - 1] * inv[i][1] % mod[i];
		}
	}
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i){
		cin >> a[i];
		hsh.A = (hsh.A + 1ll * a[i] * pw[0][i - 1] % mod[0]) % mod[0];
		hsh.B = (hsh.B + 1ll * a[i] * pw[1][i - 1] % mod[1]) % mod[1];
		sum.A = (sum.A + pw[0][i - 1]) % mod[0];
		sum.B = (sum.B + pw[1][i - 1]) % mod[1];
	}
	for (int i = 1; i <= m; ++ i)
		cin >> b[i].A, b[i].B = i;
	sort(b + 1, b + m + 1);
	for (int i = 1; i <= m; ++ i)
		swap(b[i].A, b[i].B), b[i].B = i;
	sort(b + 1, b + m + 1);
	if (m < n)
		kill(0);
	for (int i = 1; i <= n; ++ i)
		add(b[i].B, b[i].A);
	ans += (seg[1] == hsh);
	for (int i = n + 1; i <= m; ++ i){
		add(b[i].B, b[i].A), rem(b[i - n].B, b[i - n].A);
		hsh.A = (hsh.A + sum.A) % mod[0];
		hsh.B = (hsh.B + sum.B) % mod[1];
		ans += (seg[1] == hsh);
	}
	cout << ans << endl;

	return 0;
}

Compilation message (stderr)

mat.cpp: In function 'void update(int, int, int, int, int, int)':
mat.cpp:75:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |  int mid = l + r >> 1;
      |            ~~^~~
mat.cpp: In function 'void modify(int, int, int, int, pii)':
mat.cpp:87:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |  int mid = l + r >> 1;
      |            ~~^~~

• 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