QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#141112#6531. Base Station Constructioncy1999WA 1ms23032kbC++20997b2023-08-17 08:49:182023-08-17 08:49:19

Judging History

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

  • [2023-08-17 08:49:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:23032kb
  • [2023-08-17 08:49:18]
  • 提交

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'