Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!

那我怕是有幸拿了最慢吧xdd 4954ms

Posted by marszed at 2017-05-19 12:33:45 on Problem 3264
裸的RMQ 笑死了

#include<iostream>
#include<algorithm>
using namespace std;

#define maxn 50010

int n, m;
int dp_min[maxn][20], dp_max[maxn][20];

void rmq_init()
{
	for (int i = 1; i <= n; i++)
	{
		cin >> dp_min[i][0];
		dp_max[i][0] = dp_min[i][0];
	}
	for (int j = 1; 1 << j <= n; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
		{
			dp_min[i][j] = min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);
			dp_max[i][j] = max(dp_max[i][j - 1], dp_max[i + (1 << (j - 1))][j - 1]);
		}
}

int query(int l, int r)
{
	int len = 0;
	while (l + (1 << (len + 1)) - 1 <= r) len++;
	return max(dp_max[l][len], dp_max[r - (1 << len) + 1][len]) - min(dp_min[l][len], dp_min[r - (1 << len) + 1][len]);
}

int main()
{

	ios::sync_with_stdio(false);

	cin >> n >> m;
	rmq_init();
	int l, r;
	for (int i = 1; i <= m; i++)
	{
		cin >> l >> r;
		cout << query(l, r) << endl;
	}
    return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator