QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#141112 | #6531. Base Station Construction | cy1999 | WA | 1ms | 23032kb | C++20 | 997b | 2023-08-17 08:49:18 | 2023-08-17 08:49:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,t,w[500005],mn[500005],f[500005],res,ml;
struct node{
int l,r;
friend bool operator<(node a,node b){
return a.r<b.r;
}
}p[500005];
vector<int>rs[500005];
deque<int>q;
signed main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
cin>>m;
ml=0;
for(int i=1;i<=n;i++)rs[i].clear();
for(int i=1;i<=m;i++){
scanf("%lld%lld",&p[i].l,&p[i].r);
ml=max(ml,p[i].l);
}
memset(f,0x3f,sizeof(f));
f[0]=0;res=1e18;
sort(p+1,p+m+1);
mn[0]=0;
q.clear();
q.push_back(0);
for(int i=1;i<=n;i++){
while(q.size()&&q.front()<mn[i-1])q.pop_front();
f[i]=f[q.front()]+w[i];
while(q.size()&&f[q.back()]>f[i])q.pop_back();
q.push_back(i);
mn[i]=mn[i-1];
for(int j=0;j<rs[i].size();j++){
mn[i]=max(mn[i],rs[i][j]);
}
if(i>=ml)res=min(res,f[i]);
}
printf("%lld\n",res);
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 23032kb
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:
100 2
result:
wrong answer 1st numbers differ - expected: '102', found: '100'