QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#154483 | #5159. Justice Served | acm202226010311 | WA | 2ms | 7392kb | C++14 | 1.1kb | 2023-08-31 18:28:48 | 2023-08-31 18:28:48 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'