#include <bits/stdc++.h>
using namespace std;
#define LSOne(x) (x&(-x))
typedef long long int ll;
typedef long double ld;
ll t = 1;
const ll M = 1e9 + 7;
ll mod_add(ll a, ll b){
return ((a%M) + (b %M))%M;
}
ll mod_mul(ll a, ll b){
return ((a%M)*(b%M))%M;
}
const ll MAX = 1e18;
ll lcm(ll a , ll b){
return (a*b)/__gcd(a,b);
}
struct SEGTREE
{
vector<ll> values;
ll sz = 1;
SEGTREE(ll n){
while(sz <n){
sz *= 2;
}
values.assign(2*sz , 0);
}
void update(ll i , ll v , ll x , ll lx , ll rx){
if((rx - lx) == 1){
values[x] += v;
return;
}
ll m = lx + (rx - lx)/2;
if(i < m){
update(i , v , 2*x + 1, lx , m);
}
else{
update(i , v , 2*x + 2, m , rx);
}
values[x] = values[2*x + 1] + values[2*x + 2];
}
void update(ll i , ll v){
if(i>sz) return;
update(i , v , 0 , 0 , sz);
}
ll get(ll l ,ll r, ll x, ll lx , ll rx){
if((lx >= l) &&(rx<=r)) return values[x];
if((lx>=r) || (rx<=l)) return 0;
ll m = lx + (rx - lx)/2;
ll r1 = get(l , r, 2*x + 1, lx , m);
ll r2 = get(l , r , 2*x + 2, m ,rx);
return r1 + r2;
}
ll get(ll i){
return get(0 , i+1 , 0 , 0 , sz);
}
ll lb(ll i , ll v){
ll r = i, l = 0, ans = 0;
while(l<=r){
ll mid = l + (r - l)/2;
ll vmid = get(mid);
if(vmid>v){
l = mid + 1;
}
else{
ans = mid;
r = mid - 1;
}
}
return ans;
}
ll ub(ll left , ll right ,ll v){
ll l = left, r = right, ans = 0;
while(l<=r){
ll mid = l + (r - l)/2;
ll vmid = get(mid);
if(vmid<v){
r = mid - 1;
}
else{
ans = mid;
l = mid + 1;
}
}
return ans;
}
};
void solve(){
ll n ; cin>>n;
vector<vector<ll>> masts(n);
for(ll i = 0 ; i<n ;i++){
ll h , k ; cin>>h>>k;
masts[i] = {h , k};
}
sort(masts.begin(),masts.end());
ll H = masts[n-1][0];
SEGTREE sg(H);
for(int i = 0 ; i<n ; i++){
ll idx = masts[i][0] - masts[i][1];
ll k = masts[i][1];
ll he = sg.get(idx);
ll lb = sg.lb(idx , he) , ub = sg.ub(idx ,masts[i][0]-1, he);
// cout<<ub+1<<" "<<masts[i][0]<<"\n";
if(ub<(masts[i][0] - 1)){
sg.update(ub + 1, 1);
sg.update(masts[i][0], -1);
}
// cout<<lb<<" "<<(lb + k - (masts[i][0] - 1- ub))<<"\n";
sg.update(lb , 1);
sg.update(lb + k - (masts[i][0] - 1 - ub) , -1);
// for(int i = 0;i<H;i++){
// cout<<sg.get(i)<<" ";
// }
// cout<<"\n";
}
ll ans = 0;
for(int i = 0; i<H;i++){
ll r = sg.get(i);
ans += (r*(r -1))/2;
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
// freopen("input.txt" , "r" , stdin);
// freopen("output.txt" , "w", stdout);
// cin>>t;
while(t--){
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
604 KB |
Output is correct |
2 |
Correct |
12 ms |
2512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
1372 KB |
Output is correct |
2 |
Correct |
59 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
2904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
204 ms |
4688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
326 ms |
7508 KB |
Output is correct |
2 |
Correct |
260 ms |
7516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
297 ms |
8280 KB |
Output is correct |
2 |
Correct |
140 ms |
8144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
414 ms |
9124 KB |
Output is correct |
2 |
Correct |
186 ms |
7508 KB |
Output is correct |