QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#141147 | #6531. Base Station Construction | cy1999 | TL | 2ms | 7740kb | C++11 | 1.1kb | 2023-08-17 09:00:28 | 2023-08-17 09:00:29 |
Judging History
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: 7740kb
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...