QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#154483#5159. Justice Servedacm202226010311WA 2ms7392kbC++141.1kb2023-08-31 18:28:482023-08-31 18:28:48

Judging History

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

  • [2023-08-31 18:28:48]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7392kb
  • [2023-08-31 18:28:48]
  • 提交

answer

#include<iostream>
#include<algorithm>
using namespace std;
int d[1000000];
int x[1000000];
int len;
struct node
{
	int l,r;
	int id;
}qur[100005];
bool cmp(node a,node b)
{
	return a.l==b.l?a.r>b.r:a.l<b.l;
}
int lobwit(int y)
{
	return y&(-y);
}
void built()
{
	for(int i=1;i<=len;i++)
	d[i]=-1;
}
int quiry(int y )
{
	int ans=-1;
	while(y<=len)
	{
		ans=max(ans,d[y]);
		y+=lobwit(y);
	}
	return ans;
}
void unite(int y,int v)
{
	while(y>=1)
	{
		d[y]=max(v,d[y]);
		y-=lobwit(y);
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{   int a,b;
	   cin>>a>>b;
		qur[i].l=a;
		qur[i].r=a+b;
		qur[i].id=i;
		x[i*2]=a;
		x[i*2+1]=a+b;
	}
	sort(qur,qur+n,cmp);
	sort(x,x+2*n);
     len=unique(x,x+2*n)-x;
	for(int i=0;i<n;i++)
	{
		qur[i].l=lower_bound(x,x+len,qur[i].l )-x+1;
		qur[i].r=lower_bound(x,x+len,qur[i].r )-x+1;
	}
	built();
	int ans[n];
	for(int i=0;i<n;i++)
	{   int res=quiry(qur[i].r)+1;
		ans[qur[i].id]=res;
		unite(qur[i].r,res);
		
	}
	for(int i=0;i<n;i++)
	cout<<ans[i]<<endl;
	
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 7392kb

input:

4
2 8
1 7
4 5
5 2

output:

0
0
1
2

result:

wrong answer 1st lines differ - expected: '0 0 1 2', found: '0'