This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int tree[100005], lazy[400005];
vector<pair<int, int> > v;
void update(int id, int l, int r, int L, int R){
if(l == L && r == R){
lazy[id]++;
return;
}
int m = (l + r) >> 1;
if(m < L) update(id << 1 | 1, m + 1, r, L, R);
else if(m >= R) update(id << 1, l, m, L, R);
else {
update(id << 1, l, m, L, m);
update(id << 1 | 1, m + 1, r, m + 1, R);
}
}
void push(int id, int l, int r){
if(l == r) tree[l] += lazy[id];
else {
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id] = 0;
}
int query(int id, int l, int r, int x){
push(id, l, r);
if(l == r) return tree[l];
int m = (l + r) >> 1;
if(m < x) return query(id << 1 | 1, m + 1, r, x);
return query(id << 1, l, m, x);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i = 1; i <= n; i++){
int h, k;
cin>>h>>k;
v.push_back({h, k});
}
sort(v.begin(), v.end());
for(auto& x : v){
int h = x.first;
int k = x.second;
int idr = h - k + 1;
int idl = idr;
int val = query(1, 1, 100000, idr);
for(int j = 19; j >= 0; j--){
if(idl - (1 << j) > 0 && query(1, 1, 100000, idl - (1 << j)) == val) idl -= (1 << j);
if(idr + (1 << j) <= h && query(1, 1, 100000, idr + (1 << j)) == val) idr += (1 << j);
}
int ri = h - idr;
int le = k - ri;
if(le) update(1, 1, 100000, idl, idl + le - 1);
if(ri) update(1, 1, 100000, idr + 1, idr + ri);
}
long long res = 0;
for(int i = 1; i <= 100000; i++){
long long a = query(1, 1, 100000, i);
res += a * (a - 1) / 2;
}
cout<<res;
}
# | 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... |