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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
struct Point
{
int x, y;
Point() : x(0), y(0) {}
Point(int x, int y) : x(x), y(y) {}
};
int N;
Point point[MAXN+10];
ll ans;
vector<Point> tree[MAXN*4+10];
void update(int node, int tl, int tr, int pos, Point p)
{
if(pos<tl || tr<pos) return;
if(tl==tr)
{
tree[node].push_back(p);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, pos, p);
update(node*2+1, mid+1, tr, pos, p);
while(!tree[node].empty() && tree[node].back().y<p.y) tree[node].pop_back();
tree[node].push_back(p);
}
int ret, pos;
void query(int node, int tl, int tr, int l, int r)
{
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
if(tree[node].empty()) return;
ret+=tree[node].end()-lower_bound(tree[node].begin(), tree[node].end(), Point(pos, 0), [&](const Point& p, const Point& q) { return p.x<q.x; });
pos=max(pos, tree[node][0].x);
return;
}
int mid=tl+tr>>1;
query(node*2+1, mid+1, tr, l, r);
query(node*2, tl, mid, l, r);
}
int main()
{
int i, j;
scanf("%d", &N);
for(i=1; i<=N; i++) scanf("%d%d", &point[i].x, &point[i].y);
sort(point+1, point+N+1, [&](const Point& p, const Point& q) { return p.y<q.y; });
for(i=1; i<=N; i++) point[i].y=i;
sort(point+1, point+N+1, [&](const Point& p, const Point& q) { return p.x<q.x; });
for(i=1; i<=N; i++) point[i].x=i;
for(i=1; i<=N; i++)
{
ret=0, pos=-1;
query(1, 1, N, 1, point[i].y);
ans+=ret;
update(1, 1, N, point[i].y, point[i]);
}
printf("%lld", ans);
}
Compilation message (stderr)
scarecrows.cpp: In function 'void update(int, int, int, int, Point)':
scarecrows.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
scarecrows.cpp: In function 'void query(int, int, int, int, int)':
scarecrows.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:57:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
scarecrows.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
scarecrows.cpp:60:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%d%d", &point[i].x, &point[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... |