Submission #1178354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178354		vominhhuy123	Matching (CEOI11_mat)	C++20	0 / 100	993 ms	68300 KiB

mat

#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>

#define ll long long
#define ii pair<int, int>
#define pb push_back
#define ff first
#define ss second

#define LOG 22
#define N 1000826
#define oo 1000000000000000007
#define mod 1000000007

#define FOR(i, a, b)    for(int i = (a); i <= (b); ++i)
#define FORD(i, b, a)   for(int i = (b); i >= (a); --i)

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }

using namespace std;

const int base = 131;

struct Node {
	ll lazy, hash;
   	int	cnt;
} st[4*N];

int n, m;
int h[N], g[N], pos[N], q[N], l[N];
ll POW[N], HASH, sp[N];

inline ll fp(ll a, ll n) {
	ll res = 1;
	while (n) {
		if (n%2) res = res*a%mod;
		a = a*a%mod;
		n >>= 1;
	}
	return res;
}

inline Node combine(Node x, Node y) {
	return {0, (x.hash + y.hash*POW[x.cnt]%mod)%mod, x.cnt+y.cnt};
}

void init() {
	vector<ii> t;
	FOR(i, 1, n) t.pb({h[i], i});
	sort(t.begin(), t.end());
	FOR(i, 1, n) pos[i] = t[i-1].ss;
	sort(q+1, q+m+1);
	FOR(i, 1, m) l[i] = lower_bound(q+1, q+m+1, g[i]) - q;
}

void calculateHash() {
	POW[0] = 1;
	FOR(i, 1, n) POW[i] = POW[i-1]*base%mod;
	FOR(i, 1, n) HASH = (HASH + pos[i]*POW[i-1]%mod)%mod;	
	FOR(i, 1, n) sp[i] = fp(base-1, mod-2)*(POW[i]-1+mod)%mod;
}

inline void down(int i, int l, int r) {
	st[i].hash = (st[i].hash + st[i].lazy*sp[st[i].cnt]%mod + mod)%mod;
	if (l != r) {
		st[i<<1].lazy += st[i].lazy;
		st[i<<1|1].lazy += st[i].lazy;
	}
	st[i].lazy = 0;
}

void updatePoint(int i, int l, int r, int p, int v, int cnt) {
	down(i, l, r);
	if (l > p || r < p) return;
	if (l == r) {
		st[i].cnt = cnt;
		st[i].hash = v%mod;
		return;
	}
	int m = l+r>>1;
	updatePoint(i<<1, l, m, p, v, cnt);
	updatePoint(i<<1|1, m+1, r, p, v, cnt);
	st[i] = combine(st[i<<1], st[i<<1|1]);
}

void updateRange(int i, int l, int r, int u, int v, int d) {
	down(i, l, r);
    if (l > v || u > r) return;
    if (u <= l && r <= v) {
		st[i].lazy += d;
		down(i, l, r);
        return;
    }
	int m = l+r>>1;
	updateRange(i<<1, l, m, u, v, d);
	updateRange(i<<1|1, m+1, r, u, v, d);
	st[i] = combine(st[i<<1], st[i<<1|1]);
}

Node get(int i, int l, int r, int u, int v) {
	down(i, l, r);
	if (l > v || r < u) return {};
	if (l >= u && r <= v) return st[i];
	int m = l+r>>1;
	return combine(get(i<<1, l, m, u, v), get(i<<1|1, m+1, r, u, v));
}

main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	cin >> n >> m;
	FOR(i, 1, n) cin >> h[i];
	FOR(i, 1, m) {
		cin >> g[i];
		q[i] = g[i];
	}
	init();
	calculateHash();
	FOR(i, 1, n) updatePoint(1, 1, m, l[i], i, 1);
	vector<int> ans;
	auto res = get(1, 1, m, 1, m);
	if (res.cnt == n && res.hash == HASH) ans.pb(1);
	FOR(i, 2, m-n) {
		updatePoint(1, 1, m, l[i-1], 0, 0);
		updateRange(1, 1, m, 1, m, -1);
		updatePoint(1, 1, m, l[i+n-1], n, 1);
		auto res = get(1, 1, m, 1, m);
		if (res.cnt == n && res.hash == HASH) ans.pb(i);
	}
	cout << ans.size() << '\n';
	for (int x : ans) cout << x << ' ';
}

Compilation message (stderr)

mat.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main() {
      | ^~~~

• 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