#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second
const ll S = (1 << 19);
struct MinSegTree{
ll T[2 * S] = {};
void update(ll k, ll v) { update(1, 1, S, k + 1, v); }
ll query(ll l, ll r) { return query(1, 1, S, l + 1, r + 1); }
void update(ll node, ll s, ll e, ll k, ll v){
if (s == e){
T[node] = v;
return;
}
ll m = (s + e) / 2;
ll lch = 2 * node, rch = 2 * node + 1;
if (k <= m) update(lch, s, m, k, v);
else update(rch, m + 1, e, k, v);
ll x = T[lch], y = T[rch];
T[node] = min(x, y);
}
ll query(ll node, ll s, ll e, ll l, ll r){
if (e < l || s > r) return 1e15;
if (l <= s && e <= r) return T[node];
ll m = (s + e) / 2;
ll lch = 2 * node, rch = 2 * node + 1;
ll x = query(lch, s, m, l, r), y = query(rch, m + 1, e, l, r);
return min(x, y);
}
};
struct MaxSegTree{
ll T[2 * S] = {};
void update(ll k, ll v) { update(1, 1, S, k + 1, v); }
ll query(ll l, ll r) { return query(1, 1, S, l + 1, r + 1); }
void update(ll node, ll s, ll e, ll k, ll v){
if (s == e){
T[node] = v;
return;
}
ll m = (s + e) / 2;
ll lch = 2 * node, rch = 2 * node + 1;
if (k <= m) update(lch, s, m, k, v);
else update(rch, m + 1, e, k, v);
ll x = T[lch], y = T[rch];
T[node] = max(x, y);
}
ll query(ll node, ll s, ll e, ll l, ll r){
if (e < l || s > r) return 0;
if (l <= s && e <= r) return T[node];
ll m = (s + e) / 2;
ll lch = 2 * node, rch = 2 * node + 1;
ll x = query(lch, s, m, l, r), y = query(rch, m + 1, e, l, r);
return max(x, y);
}
};
MinSegTree T1;
MaxSegTree T2;
ll N;
pair<ll, ll> A[200005];
ll ans = 0;
void dnc(ll L, ll R){
if(L >= R) return;
ll m = (L + R) / 2;
vector<pair<ll, ll>> V;
for(int i = L; i <= R; i++){
V.push_back({A[i].y, i});
}
sort(V.begin(), V.end(), greater<pair<ll, ll>>());
vector<ll> B;
for(int i = 0; i < V.size(); i++){
ll K = V[i].y;
if(K <= m){
ll S = T1.query(K, m);
ll E = T2.query(S, i);
ans += B.end() - lower_bound(B.begin(), B.end(), E);
T1.update(K, i);
} else {
while(!B.empty() && B.back() > K) B.pop_back();
B.push_back(K);
T2.update(i, K);
}
}
for(int i = 0; i < V.size(); i++){
ll K = V[i].y;
T1.update(K, 0);
T2.update(K, 0);
}
dnc(L, m);
dnc(m + 1, R);
}
int main(){
cin.tie(0) -> sync_with_stdio(false);
cin >> N;
vector<ll> X, Y;
for(int i = 1; i <= N; i++){
cin >> A[i].x >> A[i].y;
X.push_back(A[i].x);
Y.push_back(A[i].y);
}
sort(A + 1, A + N + 1);
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
for(int i = 1; i <= N; i++){
A[i].x = lower_bound(X.begin(), X.end(), A[i].x) - X.begin() + 1;
A[i].y = lower_bound(Y.begin(), Y.end(), A[i].y) - Y.begin() + 1;
}
dnc(1, N);
cout << ans;
}
Compilation message
scarecrows.cpp: In function 'void dnc(ll, ll)':
scarecrows.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 0; i < V.size(); i++){
| ~~^~~~~~~~~~
scarecrows.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0; i < V.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1476 ms |
23864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
