#include<bits/stdc++.h>
#define int long long
using namespace std;
int mxn = 3*1e5+5;
/*vector<int> s(mxn*4,0),add(4*mxn,0),a(mxn,0);
void ekle(int node,int l,int r,int x,int y)
{
if(l>=x && r<=y)
{
add[node]++;
}
}*/
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<array<int,2>> val(n);
for(int i=0;i<n;i++) cin >> val[i][0] >> val[i][1];
sort(val.begin(),val.end());
vector<int> a(val.back()[0]+2,0);
int cur = 1;
for(int i=0;i<n;i++)
{
int kac = val[i][1];
int mx = val[i][0];
int son = min(mx,cur+kac-1);
int elde = max(0LL,cur+kac-1-mx);
a[cur]++;
a[son+1]--;
cur = son+1;
if(cur>mx)
{
if(elde)
{
a[1]++;
a[elde+1]--;
}
cur = elde+1;
}
}
for(int i=1;i<a.size();i++) a[i]+= a[i-1];
int sum = 0;
for(int i=1;i<a.size();i++)
{
sum+=a[i]*(a[i]-1)/2;
//cout << a[i] << endl;
}
cout << sum << endl;
}
| # | 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... |