#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll aib[100005];
ll lg;
struct date
{
ll h,k;
} v[100005];
bool comp(date a, date b)
{
return a.h<b.h;
}
int lsb(int x)
{
return x&(-x);
}
void update(int poz,int val)
{
for(int i=poz;i<=lg;i+=lsb(i))
aib[i]+=val;
}
ll query(int poz)
{
ll rez=0;
for(int i=poz;i>=1;i-=lsb(i))
rez+=aib[i];
return rez;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i].h>>v[i].k;
sort(v+1,v+n+1,comp);
lg=v[n].h;
for(int i=1;i<=n;i++)
{
ll k=v[i].k;
ll h=v[i].h;
ll nr=query(h-k+1);
ll first=h+1;
ll st=1;
ll dr=h;
while(st<=dr)
{
int mij=(st+dr)/2;
if(query(mij)<nr)
{
first=mij;
dr=mij-1;
}
else
st=mij+1;
}
if(first<=h)
{
update(first,+1);
update(h+1,-1);
}
ll lft=k-(h-first+1);
st=1;
dr=h;
first=h;
while(st<=dr)
{
int mij=(st+dr)/2;
if(query(mij)<=nr)
{
first=mij;
dr=mij-1;
}
else
st=mij+1;
}
update(first,+1);
update(first+lft,-1);
}
ll ans=0;
for(int i=1;i<=lg;i++)
{
ll val=query(i);
ans+=val*(val-1)/2;
}
cout<<ans;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
1124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
612 KB |
Output is correct |
2 |
Correct |
26 ms |
1048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
1208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
2056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
92 ms |
3080 KB |
Output is correct |
2 |
Correct |
94 ms |
3124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
103 ms |
3448 KB |
Output is correct |
2 |
Correct |
89 ms |
3020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
127 ms |
3720 KB |
Output is correct |
2 |
Correct |
85 ms |
3124 KB |
Output is correct |