M. Heaviside Function

Time Limit: 20 Sec

Memory Limit: 256 MB

題目連接

http://codeforces.com/gym/100187/problem/M

Description

Heaviside function is defined as the piecewise constant function whose value is zero for negative argument and one for non-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 by space — si and ai (si?=??±?1, ?-?109?≤?ai?≤?109) — parameters of the i-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 the function for.

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

Output

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

Sample Input

6
1 3
-1 2
1 9
-1 2
1 7
-1 2
8
0 12 2 8 4 -3 7 9

Sample Output

0
3
0
2
1
3
2
3

HINT

?

題意

if(sx-a>=0)ans++;問你每個數通過這個公式，最后的ans是多少

題解：

當s=1時，很顯然這個直線是單調向上的，我們可以利用two pointer來優化就好了

復雜度O(n+m)

代碼

#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 200101 #define mod 1000000009 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //**************************************************************************************struct node {int x,y; };bool cmp1(node a,node b) {return a.x<b.x; } bool cmp2(node a,node b) {return a.y<b.y; } node a[maxn]; vector<int> a1; vector<int> a2; node b[maxn]; int ans[maxn];int main() {int flag1=0,flag2=0;int n=read();for(int i=0;i<n;i++){a[i].x=read(),a[i].y=read();if(a[i].x==1)flag1++,a1.push_back(a[i].y);elseflag2++,a2.push_back(a[i].y);}int m=read();for(int i=0;i<m;i++)b[i].x=read(),b[i].y=i;sort(b,b+m,cmp1);sort(a1.begin(),a1.end());sort(a2.begin(),a2.end());for(int i=m-1;i>=0;i--){if(flag1==0)break;while(b[i].x<a1[flag1-1]&&flag1>0)flag1--;if(flag1==0)break;ans[b[i].y]+=flag1;}for(int i=0;i<m;i++){if(flag2==0)break;while(b[i].x>-a2[flag2-1]&&flag2>0)flag2--;if(flag2==0)break;ans[b[i].y]+=flag2;}for(int i=0;i<m;i++)printf("%d\n",ans[i]); }

?

總結

以上是生活随笔為你收集整理的Codeforces Gym 100187M M. Heaviside Function two pointer的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。