80分MLE求助
查看原帖
80分MLE求助
1219241
tiger1313楼主2023/12/16 17:09

MLE on #2,10

本蒟蒻想不明白了,难道这题不能用ST表?

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

int a;
int mn[3000005][20];
int n, m;

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9'){ if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0'&& ch <= '9'){x = x * 10 + ch - 48; ch = getchar();}
	return x * f;
}
void pre()
{
	for (int j=1; (1 << j)<=n; j++)
		for (int i=1; i + (1 << j) - 1 <= n; i++) {
			mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
		}
}
int sea(int l, int r)
{
	int len = log2(r - l + 1);
	return min(mn[l][len], mn[r - (1 << len) + 1][len]);
}
int main()
{
	n = read();
	m = read();
	for (int i=1; i<=n; i++) {
		a = read();
		mn[i][0] = a;
	}
	pre();
	cout << "0" << endl;
	for (int i=1; i<n; i++) {
		int l = i - m + 1 , r = i;
		if (l < 1) l = 1;
		printf("%d\n", sea(l, r));
	}
	return 0;
}
2023/12/16 17:09
加载中...