#include<bits/stdc++.h>
using namespace std;
vector<int> t, t2, L;
inline void prop(int i, int s, int e){
if(s != e){
L[i*2] += L[i];
L[i*2+1] += L[i];
}
t[i] += L[i];
t2[i] += L[i];
L[i] = 0;
}
void upd(int i, int s, int e, int l, int r){
prop(i, s, e);
if(l <= s && e <= r){
L[i] += 1;
prop(i, s, e);
return;
}
if(s > r || e < l || s > e){
return;
}
int m = (s + e)/2;
upd(i*2, s, m, l, r);
upd(i*2+1, m+1, e, l, r);
t[i] = max(t[i*2], t[i*2+1]);
t2[i] = min(t2[i*2], t2[i*2+1]);
}
int query(int i, int s, int e, int indx){
prop(i, s, e);
if(s == e) return t[i];
int m = (s + e)/2;
if(indx <= m) return query(i*2, s, m, indx);
else return query(i*2+1, m+1, e, indx);
}
int right(int i, int s, int e, int l, int r, int val){
prop(i, s, e);
if(s > e || s > r || e < l) return -1;
if(t[i] < val) return -1;
if(l <= s && e <= r){ //completely inside
if(s == e) return s;
}
int m = (s + e)/2;
int ri = right(i*2+1, m+1, e, l, r, val);
if(ri == -1) return right(i*2, s, m, l, r, val);
else return ri;
}
int left(int i, int s, int e, int l, int r, int val){
prop(i, s, e);
if(s > e || s > r || e < l) return -1;
if(t2[i] > val) return -1;
if(l <= s && e <= r){
if(s == e) return s;
}
int m = (s + e)/2;
int le = left(i*2, s, m, l, r, val);
if(le != -1) return le;
return left(i*2+1, m+1, e, l, r, val);
}
void print(int i, int s, int e){
prop(i, s, e);
if(s == e){
cout<<"S: "<<t[i]<<endl;
return;
}
int m = (s + e)/2;
print(i*2, s, m);
print(i*2+1, m+1, e);
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
int N; cin>>N;
vector<pair<int, int> > a(N);
int n = 100;
for(int i = 0; i < N; i++){
cin>>a[i].first>>a[i].second;
n = max(n, a[i].first);
}
sort(a.begin(), a.end());
t = vector<int>(4*n, 0);
t2 = vector<int>(4*n, 0);
L = vector<int>(4*n, 0);
for(int i = 0; i < N; i++){
int h = a[i].first, k = a[i].second;
//need to insert k masts in the end
//cout<<"ADDING "<<h<<" "<<k<<endl;
int v = query(1, 0, n-1, h-k);
int l = left(1, 0, n-1, 0, h-1, v);
int r = right(1, 0, n-1, 0, h-1, v);
//cout<<v<<" "<<l<<" "<<r<<endl;
if(r != h-1) upd(1, 0, n-1, r+1 ,h-1);
upd(1, 0, n-1, l, l-1 + k-(h-r-1));
//cout<<"UPDING FROM "<<l<<" "<<l-1 + (k-(h-r-1))<<" and "<<r+1<<" "<<h-1<<endl;
//print(1, 0, n-1);
}
long long ans = 0;
for(int i = 0; i < n; i++){
long long v = query(1, 0, n-1, i);
//cout<<i<<" : "<<v<<endl;
ans = (ans + v*(v-1)/2);
}
cout<<ans<<endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
21 ms |
5084 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
1912 KB |
Output is correct |
| 2 |
Correct |
61 ms |
888 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
80 ms |
2172 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
151 ms |
3268 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
259 ms |
5808 KB |
Output is correct |
| 2 |
Correct |
227 ms |
5752 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
277 ms |
5928 KB |
Output is correct |
| 2 |
Correct |
152 ms |
5404 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
329 ms |
6036 KB |
Output is correct |
| 2 |
Correct |
207 ms |
2748 KB |
Output is correct |
