제출 #991667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991667		vjudge1	Matching (CEOI11_mat)	C++17	100 / 100	1704 ms	52564 KiB

mat

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int fast_power(int n, int m){
	int res = 1;
	while (m){
		if (m % 2)
			res = 1ll * res * n % mod;
		n = 1ll * n * n % mod;
		m >>= 1;
	}
	return res;
}

const int BASE = MAXN;
const int INV_BASE = fast_power(BASE, mod - 2);

struct BIT {
	int t[MAXN];
	void add(int p, int v){
		for (p += 5; p < MAXN; p += p & -p){
			t[p] += v;
		}
	}
	int get(int p){
		int res = 0;
		for (p += 5; p; p -= p & -p){
			res += t[p];
		}
		return res;
	}
} bit;
const int off = (1<<20);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
	int t[off << 1], lazy[off << 1];
	void init(){
		for (int i = 0; i < off * 2; i++) lazy[i] = 1;
	}
	int unit = 0;
	void pull(int idx){
		t[idx] = (t[ls] + t[rs]) % mod;
	}
	void update(int idx, int u){
		t[idx+=off] = u;
		while (idx/=2)
			pull(idx);
	}
	void push(int idx){
		if (lazy[idx] == 1) return;
		t[idx] = 1ll * t[idx] * lazy[idx] % mod;
		if (idx < off){
			lazy[ls] = 1ll * lazy[ls] * lazy[idx] % mod;
			lazy[rs] = 1ll * lazy[rs] * lazy[idx] % mod;
		}
		lazy[idx] = 1;
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		push(idx);
		if (r <= lo || hi <= l) 
			return unit;
		if (l <= lo && hi <= r)
			return t[idx];
		int mi = (lo+hi)>>1;
		return (get(l, r, ls, lo, mi) + get(l, r, rs, mi, hi)) % mod;
	}
	void mul_update(int l, int r, int val, int idx=1, int lo=0, int hi=off){
		push(idx);
		if (r <= lo || hi <= l) 
			return ;
		if (l <= lo && hi <= r){
			lazy[idx] = 1ll * lazy[idx] * val;
			push(idx);
			return ;
		}
		int mi = (lo+hi)>>1;
		mul_update(l, r, val, ls, lo, mi);
		mul_update(l, r, val, rs, mi, hi);
		pull(idx);
	}
	void add_update(int l, int r, int val, int idx=1, int lo=0, int hi=off){
		push(idx);
		if (r <= lo || hi <= l) 
			return ;
		if (l <= lo && hi <= r){
			t[idx] = val;
			return ;
		}
		int mi = (lo+hi)>>1;
		add_update(l, r, val, ls, lo, mi);
		add_update(l, r, val, rs, mi, hi);
		pull(idx);
	}
} seg;
int a[MAXN], b[MAXN];
int powers[MAXN];
int m, n;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	seg.init();
	cin >> m >> n;
	for (int i = 1; i <= m; i++){
		cin >> b[i];
	}
	vector<int> deco(n);
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		deco[i - 1] = a[i];
	}
	sort(all(deco));
	for (int i = 1; i <= n; i++){
		a[i] = lower_bound(all(deco), a[i]) - deco.begin() + 1;
	}
	int perm_hash = 0;
	int sum = 0;
	powers[0] = 1;
	for (int i = 1; i <= m; i++){
		powers[i] = 1ll * powers[i - 1] * BASE % mod;
		perm_hash += 1ll * b[i] * powers[i] % mod;
		sum += powers[i];

		if (sum >= mod) sum -= mod;
		if (perm_hash >= mod) perm_hash -= mod;
	}

	for (int i = 1; i < m; i++){
		bit.add(a[i], 1);
	}
	for (int i = 1; i < m; i++){
		seg.add_update(a[i], a[i] + 1, 1ll * powers[bit.get(a[i])] * i % mod); 
	}
	vector<int> ans;
	for (int i = 1; i + m - 1 <= n; i++){
		int r = i + m - 1;
		bit.add(a[r], 1);
		// insert number r at postion a[r] with power bit.get(a[r]) and increase every power after it
		seg.add_update(a[r], a[r] + 1, 1ll * powers[bit.get(a[r])] * r % mod); 
		seg.mul_update(a[r] + 1, off, BASE); 
		if (seg.get(0, off) == perm_hash){
			ans.pb(i);
		}
		seg.add_update(a[i], a[i] + 1, 0);
		seg.mul_update(a[i] + 1, off, INV_BASE);
		bit.add(a[i], -1);
		perm_hash += sum;
		if (perm_hash >= mod) perm_hash -= mod;
	}
	cout << sz(ans) << endl;
	for (auto x : ans) cout << x << ' ';
}

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