#pragma GCC optimize("O5,unroll-loops,inline,fast-math")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
const int N=1e5+5;
int t[N],n,ans=0;
pair<int,int> a[N];
void up(int i, int v) {for (; i < N; i += i&-i) t[i] += v;}
int q(int i) {
int sum=0;
for (; i > 0; i -= i&-i) sum += t[i];
return sum;
}
int get(int x) {
int l=0,r=N-1,m;
while (l < r) m=(l+r+1)>>1, q(m)>=x ? l=m : r=m-1;
return l;
}
signed main(void) {
exoworldgd;
cin >> n;
for (int i=0 ;i< n; i++) cin >> a[i].first >> a[i].second;
sort(a,a+n);
for (int i=0,l,r,v;i < n;i ++) v=q(a[i].first-a[i].second+1),l=get(v+1),r=min(get(v),a[i].first), up(r+1,1), up(a[i].first+1,-1), up(l+1,1), up(l+r+a[i].second-a[i].first+1,-1);
for (int i=1,v; i < N; i++) v=q(i), ans+=v*(v-1)/2;
cout << ans;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |