离谱
查看原帖
离谱
248359
Cloote楼主2021/7/21 16:33

不加快读64pts,加了快读RE的RE,WA的WA,该TLE的还是TLE(好吧我是个蒟蒻)

以下是未加快读的写法:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dp[N][30],b[N];
int main(){
	ios::sync_with_stdio(false);
	//cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	    cin>>dp[i][0];
	    b[i]=log2(i);
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
			//cout<<dp[i][j]<<" ";
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		int j=b[r-l+1];
		cout<<max(dp[l][j],dp[r-(1<<j)+1][j])<<"\n";
	}
	return 0;
}
2021/7/21 16:33
加载中...