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;
using ll = long long;
using pii = pair<int, int>;
#define X first
#define Y second
const int N = 200005, inf = int(2e9);
int n, ac, bc;
pii a[N], b[N], as[N], bs[N];
ll f(int s, int e){
if(s == e){
b[s] = a[s];
return 0;
}
int m = (s + e) / 2;
ll r = f(s, m) + f(m + 1, e);
int p, q, cc = s;
as[0] = {inf, -inf}; bs[0] = {-inf, -inf + 1};
ac = bc = 1;
for(p = s, q = m + 1; p <= m || q <= e; ){
if(q > e || (p <= m && b[p].Y < b[q].Y)){
a[cc++] = b[p];
while(as[ac - 1].X < b[p].X) ac--;
as[ac++] = b[p++];
}
else{
a[cc++] = b[q];
while(bs[bc - 1].X > b[q].X) bc--;
r += int(as + ac -
lower_bound(as, as + ac, bs[bc - 1], [](pii p, pii q){
return p.Y < q.Y;
}));
bs[bc++] = b[q++];
}
}
for(int i = s; i <= e; i++) b[i] = a[i];
return r;
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d%d", &a[i].X, &a[i].Y);
}
sort(a, a + n);
printf("%lld\n", f(0, n - 1));
}
Compilation message (stderr)
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
scarecrows.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i].X, &a[i].Y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |