Gym 100187M - Heaviside Function

Heaviside function is defined as the piecewiseconstant function whose value is zero for negative argument and one fornon-negative argument:

You are given the function f(x) = θ(s1x - a1) + θ(s2x - a2) + ... + θ(snx - an), where si =  ± 1. Calculate its values for argument values x1, x2, ..., xm.

Input

The first line contains a single integer n (1 ≤ n ≤ 200000) —the number of the summands in the function.

Each of the next n lines contains two integers separated byspace — si and ai (si =  ± 1,  - 109 ≤ ai ≤ 109) — parameters of thei-th summand.

The next line contains a single integer m (1 ≤ m ≤ 200000) —the number of the argument values you should calculate the value of thefunction for.

The last line contains m integers x1, ..., xm ( - 109 ≤ xi ≤ 109) separated by spaces — the argument valuesthemselves.

Output

Output m lines. i-th line should contain the value of f(xi).

Sample test(s)

input

6

1 3

-1 2

1 9

-1 2

1 7

-1 2

8

0 12 2 8 4 -3 7 9

output

3

2

1

3

2

3

思路：

将s=1與s=-1的分開分别用a1,a2兩個數組存儲，分别從小到大排序；

x用結構存儲，記錄值和輸入順序，并按數值從小到大排序；

對于s=1，即對于a1數組，則統計x-a1[i]>=0的個數，我們可以枚舉x，a1[i]從最大的開始，當a[i]足夠小時，統計a1[i]的剩餘個數。因為我們事先已經排序，是以直接加就可以；

對于s=-1的情況，同理；

代碼：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 200005;
int n, s;
int a1[N], a2[N];
int l1, l2;
int m;

struct node
{
	int value, id;
}x[N];

__int64 ans[N];

bool cmp(node a, node b)
{
	return a.value<b.value;
}

bool cmp2(node a, node b)
{
	return a.id<b.id;
}

int main()
{
	memset(ans, 0, sizeof(ans));
	scanf("%d", &n);

	int i, temp;
	l1 = l2 = 0;
	for (i = 0; i<n; i++)
	{
		scanf("%d%d", &s, &temp);
		if (s == 1)
			a1[l1++] = temp;
		else
			a2[l2++] = temp;
	}

	scanf("%d", &m);
	for (i = 0; i<m; i++)
	{
		scanf("%d", &x[i].value);
		x[i].id = i;
	}

	sort(a1, a1 + l1);
	sort(a2, a2 + l2);
	sort(x, x + m, cmp);

	for (i = m - 1; i >= 0; i--)
	{
		if (l1 == 0)
			break;
		while (x[i].value<a1[l1 - 1] && l1>0)
			l1--;
		if (l1 == 0)
			break;
		ans[x[i].id] += l1;
	}

	for (i = 0; i<m; i++)
	{
		if (l2 == 0)
			break;
		while (x[i].value>-a2[l2 - 1] && l2>0)
			l2--;
		if (l2 == 0)
			break;
		ans[x[i].id] += l2;
	}

	sort(x, x + m, cmp2);

	for (i = 0; i<m; i++)
		printf("%I64d\n", ans[i]);

	return 0;
}