提高2信号传输求调

0分,代码如下:

#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn = 2e5 + 10;
struct node
{
	int x,y;
	bool operator <(const node & b)const
	{
		if(x == b.x)
		{
			return y < b.y;
		}
		return x < b.x;
	}
}a[maxn],stk[maxn];
int top;
int serch(node x)
{
	int l = 1,r = top,ans = 0;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(stk[mid] < x)
		{
			r = mid - 1;
			ans = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	return ans;
}
int solve(int l,int r)
{
	if(l >= r)return 0;
	int mid = l + r >> 1;
	int ans = solve(l,mid) + solve(mid + 1,r);
	for(int i = mid + 1;i <= r;i++)
	{
		while(stk[top].x <= a[i].x && top > 0)
		{
			top--;
		}
		stk[++top] = a[i];
	}
	for(int i = 1;i <= top;i++)
	{
		cout << stk[i].x << " " << stk[i].y << '\n';
	}
	cout << '\n';
	for(int i = l;i <= mid;i++)
	{
		ans += serch(a[i]);
	}
	return ans;
}
/*
4
0 0
2 2
4 3
3 4
*/
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i].x >> a[i].y;
	}
	sort(a + 1,a + n + 1);
	cout << solve(1,n);
	return 0;
}
3 个赞

题面

3 个赞