#include #include #include #include #include #include #include using namespace std; const int MAX_INT = 1<<30; struct Node{ int mn,mx; int sum,n; int ltime,rtime; }; void build(vector &tree,vector &time,vector &value, int l,int r,int v){ Node ans; //printf("%d %d\n",l,r); if(l==r){ ans.mn = value[l]; ans.mx = value[l]; ans.sum = value[l]; ans.n = 1; ans.ltime = time[l]; ans.rtime = time[l]; tree[v] = ans; return; } int mid = (l+r)/2; build(tree,time,value,l,mid,2*v); build(tree,time,value,mid+1,r,2*v+1); Node left = tree[2*v]; Node right = tree[2*v+1]; ans.mn = min(left.mn,right.mn); ans.mx = max(left.mx,right.mx); ans.sum = left.sum+right.sum; ans.n = left.n + right.n; ans.ltime = left.ltime; ans.rtime = right.rtime; tree[v] = ans; return; } int fmin(vector &tree,int l,int r,int ltime,int rtime,int v){ //printf("%d %d : %d %d || %d %d\n",l,r,ltime,rtime,tree[v].ltime, tree[v].rtime); if(tree[v].ltime>rtime || tree[v].rtime=ltime && tree[v].rtime<=rtime) return tree[v].mn; if(l==r){ return tree[v].mn; } int mid = (l+r)/2; int a1 = fmin(tree,l,mid,max(ltime,tree[v].ltime),min(rtime,tree[v].rtime),2*v); int a2 = fmin(tree,mid+1,r,max(ltime,tree[v].ltime),min(rtime,tree[v].rtime),2*v+1); return min(a1,a2); } int fmax(vector &tree,int l,int r,int ltime,int rtime,int v){ //printf("%d %d : %d %d || %d %d\n",l,r,ltime,rtime,tree[v].ltime, tree[v].rtime); if(tree[v].ltime>rtime || tree[v].rtime=ltime && tree[v].rtime<=rtime) return tree[v].mx; if(l==r){ return tree[v].mx; } int mid = (l+r)/2; int a1 = fmax(tree,l,mid,max(ltime,tree[v].ltime),min(rtime,tree[v].rtime),2*v); int a2 = fmax(tree,mid+1,r,max(ltime,tree[v].ltime),min(rtime,tree[v].rtime),2*v+1); return max(a1,a2); } pair fsum(vector &tree,int l,int r,int ltime,int rtime,int v){ //printf("%d %d : %d %d || %d %d\n",l,r,ltime,rtime,tree[v].ltime, tree[v].rtime); if(tree[v].ltime>rtime || tree[v].rtime=ltime && tree[v].rtime<=rtime) return make_pair(tree[v].sum,tree[v].n); if(l==r){ return make_pair(tree[v].sum, tree[v].n); } int mid = (l+r)/2; pair a1 = fsum(tree,l,mid,max(ltime,tree[v].ltime),min(rtime,tree[v].rtime),2*v); pair a2 = fsum(tree,mid+1,r,max(ltime,tree[v].ltime),min(rtime,tree[v].rtime),2*v+1); return make_pair(a1.first+a2.first, a1.second+a2.second); } int main(){ //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); ios::sync_with_stdio(false); int n; while(cin>>n){ vector time(n),value(n); for(int i=0;i> time[i] >> value[i]; vector tree(4*n); build(tree,time,value,0,n-1,1); int m; cin >> m; for(int k=0;k> lg >> fnc >> sec; int ans = 0; for(int i=1;i lres = fsum(tree,0,n-1,time[i]-sec,time[i]-1,1); res = lres.first/(double)lres.second; }else if(fnc=="max"){ res = fmin(tree,0,n-1,time[i]-sec,time[i]-1,1); } if(lg=="lt"){ ans+=(value[i]res)?1:0; } } cout << ans << endl; //cout << endl; } } return 0; }