// Src : Vux2Code
/* Note :
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front
#define vec3d vector<vector<vector<ll>>>
#define vec2d vector<vector<ll>>
#define vec1d vector<ll>
vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}
template<typename T>
using rvs_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
#define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
#define foreach(i, j) for (ll i : (j))
#define all(a) (a).begin (), (a). end ()
#define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())
const ll maxN = 1e5 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;
void maxi(ll &x, ll y) { x = max(x, y); }
void mini(ll &x, ll y) { x = min(x, y); }
/* ---------HASHING-------- */
// const base = 31, mod2 = 1e9 + 9;
/* ---------BITMASK-------- */
// ll count(ll x) { return __builtin_popcountll(x); }
// ll fst(ll x) { return 63 - __builtin_clzll(x); }
// ll last(ll x) { return __builtin_ctzll(x); }
// bool bit(ll x, ll y) { return ((x >> y) & 1); }
ll t = 1;
struct BIT {
vector <ll> f;
ll n;
BIT (ll x) :
n (x)
,f (x + 1, 0)
{}
void update (ll x, ll v) {
while (x <= n) {
f [x] += v;
x += (x & -x);
}
}
ll get (ll x) {
ll ans = 0;
while (x > 0) {
ans += f [x];
x -= (x & -x);
}
return ans;
}
};
struct LaziBIT {
BIT add, mul;
ll n;
LaziBIT (ll x) :
add (x), mul (x), n (x) {}
void update (ll l, ll r, ll v) {
mul. update (l, v);
mul. update (r + 1, -v);
add. update (l, -v * (l - 1));
add. update (r + 1, r * v);
}
ll get (ll x) {
return mul. get (x) * x + add. get (x);
}
ll getRange (ll x, ll y) {
return get (y) - get (x - 1);
}
}f (maxN);
ll finmin (ll l, ll r, ll val) {
ll mid, ans = l;
while (l <= r) {
ll mid = (l + r) >> 1;
//cerr << "How the fick : " << l << ' ' << r << ' ' << mid << ' ' << f. getRange (mid, mid) << ' ' << val << '\n';
if (f. getRange (mid, mid) <= val) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
ll finmax (ll l, ll r, ll val) {
ll mid, ans = r;
while (l <= r) {
ll mid = (l + r) >> 1;
if (f. getRange (mid, mid) >= val) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
return ans;
}
ll n;
pll a [maxN];
void solve() {
cin >> n;
forinc (i, 1, n) cin >> a [i]. fi >> a [i]. se;
sort (a + 1, a + n + 1);
//forinc (i, 1, n) cerr << a [i]. fi << ' ' << a [i]. se << '\n';
ll ans = 0;
forinc (i, 1, n) {
//forinc (j, 1, n) cerr << f. getRange (j, j) << ' '; cerr << '\n';
ll tmp = a [i]. fi - a [i]. se + 1;
ans += f. getRange (tmp, a [i]. fi);
ll val = f. getRange (tmp, tmp);
ll l = finmin (1, a [i]. fi, val);
ll r = finmax (1, a [i]. fi, val);
f. update (r + 1, a [i]. fi, 1);
ll nen = l + (r - tmp);
f. update (l, nen, 1);
/*
cerr << i << ' ' << a [i]. fi << ' ' << a [i]. se << '\n';
cerr << tmp << ' ' << val << '\n';
cerr << l << ' ' << nen << '\n';
cerr << r + 1 << ' ' << a [i]. fi << '\n';
cerr << ans << '\n';
forinc (j, 1, n) cerr << f. getRange (j, j) << ' '; cerr << '\n';
cerr << "\n";
*/
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define TASK "untitled1"
if (fopen (TASK".inp", "r")) {
freopen (TASK".inp", "r", stdin);
freopen (TASK".out", "w", stdout);
}
//cin >> t;
while (t--) solve();
}
Compilation message (stderr)
sails.cpp: In function 'int main()':
sails.cpp:161:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | freopen (TASK".inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:162:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | freopen (TASK".out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |