QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141146#6531. Base Station Constructioncy1999TL 2ms7752kbC++1.1kb2023-08-17 08:59:382023-08-17 08:59:42

Judging History

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

  • [2023-08-17 08:59:42]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:7752kb
  • [2023-08-17 08:59:38]
  • 提交

answer

#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];
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 ans1=ask(l,r)+find1(w[p].l,w[p].r,p+1);
	int ans2=ask(w[p].l,w[p].r)+find1(l,r,p+1);
	int ans3=find1(w[p].l,r,p+1);
	int ans=min(min(ans1,ans2),ans3);
	return ans;
}
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		yuchuli();
		cin>>m;
		for(int i=1;i<=m;i++)
		{
			cin>>w[i].l>>w[i].r;
		}
		a[n+1]=0;
		w[m+1].l=w[m+1].r=n+1;
		int ans=find1(0,0,1);
		cout<<ans<<endl;
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7752kb

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:

61
48
4
19
94
68
23
2
43
113
74
52
68
48
185
32
59
89
8
84
35
23
1
6
100
93
236
145
56
100
237
57
46
18
17
24
10
88
20
32
35
103
44
38
90
33
16
109
72
29
54
79
272
182
109
26
376
34
65
16
30
33
24
36
72
100
81
105
106
14
73
57
71
38
211
53
5
17
166
82
93
63
36
24
97
33
117
8
19
35
116
64
116
40
36
7...

result: