Submission #1263269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263269		_rain_	Matching (CEOI11_mat)	C++20	100 / 100	584 ms	59012 KiB

mat

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

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1)<<(x))
#define sz(x) (int)(x).size()

template<class T1 , class T2>
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1,class T2>
	T2 Find(vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}

const int N = (int) 1e6;
	int n , m;
	int rnk[N + 2] , mx[N + 2] , mn[N + 2] , pos[N + 2];

class IT{
	public:
		vector<int> mx , mn;
		void load_size(int n){
			mx = vector<int>(n*4+2,0);
			mn = vector<int>(n*4+2,n+1);
			return;
		}
		void upd(int id , int l , int r , int pos , int val){
			if (l == r) mx[id] = mn[id] = val;
			else {
				int m = (l + r) / 2;
				if (pos <= m) upd(id * 2 , l , m , pos , val);
					else upd(id * 2 + 1 , m + 1 , r , pos , val);
				mx[id] = max(mx[id * 2] , mx[id * 2 + 1]);
				mn[id] = min(mn[id * 2 ] , mn[id * 2 + 1]);
			}
			return;
		}
		int Get_max(int id , int l , int r , int u , int v){
			if (l > v || r < u) return 0;
			if (u <= l && r <= v) return mx[id];
			int m = (l + r) / 2;
			return max(Get_max(id * 2 , l , m , u , v) , Get_max(id * 2 + 1 , m + 1 ,r , u , v));
		}
		int Get_min(int id , int l , int r , int u , int v){
			if (l > v || r < u) return (int)1e9;
			if (u <= l && r <= v) return mn[id];
			int m = (l + r) / 2;
			return min(Get_min(id * 2 , l , m , u , v) , Get_min(id * 2 + 1 , m + 1 ,r , u , v));
		} 
} st;

bool ismorphic(int cur_id , int i){
	int lef_mx = mn[cur_id];
	int rig_mx = mx[cur_id];
	if (lef_mx){
		int t = cur_id - lef_mx;
		if (rnk[i - t] > rnk[i]) return false;
	}
	if (rig_mx){
		int t = cur_id - rig_mx;
		if (rnk[i - t] < rnk[i]) return false;
	}
	return true;
}

	int kmp[N + 2] = {} , f[N + 2] = {};
	int h[N + 2] = {};
	
	
bool check(int cur_id , int i){
	if (cur_id == n + 1) return false;
	int lef_mx = mn[cur_id];
	int rig_mx = mx[cur_id];
	if (lef_mx){
		int t = cur_id - lef_mx;
		if (h[i - t] > h[i]) return false;
	}
	if (rig_mx){
		int t = cur_id - rig_mx;
		if (h[i - t] < h[i]) return false;
	}
	return true;
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> m;
		for(int i = 1; i <= n; ++i) {
			cin >> pos[i];
			rnk[pos[i]] = i;
		}
		st.load_size(n);
		for(int i = 1; i <= n; ++i) {
			mn[i] = pos[st.Get_max(1 , 1 , n , 1 , rnk[i])];
			mx[i] = pos[st.Get_min(1 , 1 , n , rnk[i] , n)];
			st.upd(1 , 1 , n , rnk[i] , rnk[i]);
		}
		kmp[1] = 0;
		for(int i = 2; i <= n; ++i){
			int cur = kmp[i - 1];
			while (cur > 0 && ismorphic(cur + 1 , i) == false) cur = kmp[cur];
			if (ismorphic(cur + 1 , i)) kmp[i] = ++cur; else kmp[i] = 0;
		}
		for(int i = 1; i <= m; ++i) cin >> h[i];
		for(int i = 1; i <= m; ++i){
			int cur = f[i - 1] ;
			while (cur > 0 && check(cur + 1 , i) == false) cur = kmp[cur];
			if (check(cur + 1 , i)) f[i] = cur + 1; else f[i] = 0;
		}
		vector<int>ans;
		for(int i = 1; i <= m; ++i) {
			if (f[i] == n) ans.push_back(i - n + 1);
		}
		cout << sz(ans) << '\n';
		for(int x : ans) cout << x << ' ';
	return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:104:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mat.cpp:105:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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