QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#141316	#6531. Base Station Construction	cy1999	TL	2ms	7868kb	C++11	2.3kb	2023-08-17 10:43:13	2023-08-17 10:43:15

Judging History

你现在查看的是最新测评结果

[2023-08-17 10:43:15]
评测

测评结果：TL
用时：2ms
内存：7868kb

查看

[2023-08-17 10:43:13]
提交

answer

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int t,n,m;
int f[N][30];
int a[N];
map<int ,int> q;
int read()
{
	int res=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		res=10*res+c-'0';
		c=getchar();
	}
	return res;
}
struct node
{
	int l,r;
}w[N];
void yuchuli()
{
	for(int i=1;i<=n;i++)
	{
		f[i][0]=a[i];
	}
	int p=log(n)/log(2);
	for(int j=1;j<=p;j++)
	{
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int ask(int l,int r)
{
	int p=log(r-l+1)/log(2);
	return min(f[l][p],f[r-(1<<p)+1][p]);
}
//int find1(int l,int r,int p)
//{
//	if(p==m+1)
//	{
//		return ask(l,r);
//	}
//	if(r<w[p].l)
//	{
//		return ask(l,r)+find1(w[p].l,w[p].r,p+1);
//	}
//	if(w[p].l>=l&&w[p].r<=r)
//	{
//		return find1(w[p].l,w[p].r,p+1);
//	}
//	
//}
int find2(int l,int r,int p)
{
	if(p==m)
	{
		if(!l&&!r)
		{
			return ask(w[p].l,w[p].r );
		}
		int ans1=ask(l,w[p].l)+ask(r,w[p].r);
		int ans2=ask(w[p].l,r);
		return min(ans1,ans2);
	}
	if(r<w[p].l)
	{
		if(q[p])
		{
			return q[p];
		}
		int num=ask(l,r);
		if(w[p+1].l>w[p].r)
		{
			if(!l&&!r)
			{
				return q[p]=ask(w[p].l,w[p].r)+find2(0,0,p+1);
			}
			return ask(l,r)+ask(w[p].l,w[p].r)+find2(0,0,p+1);
		}
		if(!l&&!r)
		{
			return q[p]=find2(w[p].l,w[p].r,p+1);
		}
		return ask(l,r)+find2(w[p].l,w[p].r,p+1);
	}
	if(w[p].l>=l&&w[p].r<=r)
	{
		if(w[p+1].l>w[p].r)
		{
			return  ask(w[p].l,w[p].r)+find2(0,0,p+1);
		}
		return find2(w[p].l,w[p].r,p+1);
	}
	if(w[p+1].l>w[p].r)
	{
		int ans1=ask(l,w[p].l)+ask(r,w[p].r);
		int ans2=ask(w[p].l,r);
		return min(ans1,ans2)+find2(0,0,p+1);
	}
	if(w[p+1].l>r)
	{
		return ask(l,r)+find2(r,w[p].r,p+1);
	}
	int ans1=ask(l,r)+find2(r,w[p].r,p+1);
	int ans2=find2(w[p].l,r,p+1);
	int ans=min(ans1,ans2);
	return ans;
}
signed main()
{
//	std::ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		q.clear();
		n=read();
		for(int i=1;i<=n;i++)
		{
			a[i]=read();
		}
		yuchuli();
		m=read();
		for(int i=1;i<=m;i++)
		{
			w[i].l=read();
			w[i].r=read();
		}
		//a[n+1]=0;
		//w[m+1].l=w[m+1].r=n+1;
		int ans=find2(0,0,1);
		//cout<<ans<<endl;
		printf("%lld\n",ans);
	}
}

源文件, 语言: C++11

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 7868kb

input:

2
5
3 2 4 1 100
3
1 3
2 4
5 5
5
7 3 4 2 2
3
1 4
2 3
4 5

output:

102
5

result:

ok 2 number(s): "102 5"

Test #2:

score: -100

Time Limit Exceeded

input:

6201
12
88 78 46 95 84 98 55 3 68 42 6 18
19
6 9
10 11
12 12
8 11
8 12
2 3
2 3
1 5
9 9
7 8
6 11
2 4
12 12
2 4
2 9
7 10
8 8
1 7
6 11
5
76 27 48 66 61
2
1 4
3 5
8
64 81 20 6 86 9 4 55
1
7 7
9
1 43 18 81 11 22 9 61 83
14
5 6
2 6
5 8
1 4
9 9
9 9
7 7
2 5
8 9
5 6
4 8
5 8
9 9
6 6
10
66 41 84 7 80 31 22 96 ...

output: