#include #define REP(i, n) for(int i=0; i0; i--) tree[i] = tree[2*i] + tree[2*i+1]; } void add(int i, int h) { int k = N + i; while (k>0) { tree[k] += h; k /= 2; } } int get_sums(int A, int B) { int S = 0; int a = N + A - 1; int b = N + B + 1; while(a/2!=b/2){ if(a%2==0) S += tree[a^1]; if(b%2==1) S += tree[b^1]; a /= 2; b /= 2; } return S; } /// // //MINIMOVY int min (int a, int b){ if (b == 0) return a; if(a < b && a != 0) return a; else return b; } void inicMin(){ int leaves = 1; while(leaves0; i--) treeMin[i] = min(treeMin[2*i], treeMin[2*i+1]); } void addMin(int i, int h) { int k = N + i; while (k>0) { treeMin[k] = min(h, treeMin[k]); k /= 2; } } int get_sumsMin(int A, int B) { int S = 0, S1 = 0, S2 = 0; int a = N + A - 1; int b = N + B + 1; while(a/2!=b/2){ if(a%2==0) S1 = min(S1, treeMin[a^1]); if(b%2==1) S2 = min(S2, treeMin[b^1]); S = min(S1, S2); a /= 2; b /= 2; } return S; } //Maximovy int max (int a, int b){ if (b == 0) return a; if(a > b && a != 0) return a; else return b; } void inicMax(){ int leaves = 1; while(leaves0; i--) treeMax[i] = max(treeMax[2*i], treeMax[2*i+1]); } void addMax(int i, int h) { int k = N + i; while (k>0) { treeMax[k] = max(h, treeMax[k]); k /= 2; } } int get_sumsMax(int A, int B) { int S = 0, S1 = 0, S2 = 0; int a = N + A - 1; int b = N + B + 1; while(a/2!=b/2){ if(a%2==0) S1 = max(S1, treeMax[a^1]); if(b%2==1) S2 = max(S2, treeMax[b^1]); S = max(S1, S2); a /= 2; b /= 2; } return S; } vector > mer; int main(){ int p, dlzka, cas, hod, podmienky; string op, smer; while(cin >> p){ int mapovanie[MAXN]; for(int i = 1; i <= p; i++){ cin >> cas >> hod; //mer.push_back(make_pair(cas, hod)); seq[i] = hod; mapovanie[i] = cas; } /*for(int i = 1; i <= p; i++){ cout << seq[i] << ": " << mapovanie[i] << endl ; } cout << "spam" << endl; */ N = p; int NN = N; inic(); N = NN; inicMin(); N = NN; inicMax(); //cout << get_sums(2,4); cin >> podmienky ; for(int j = 0; j < podmienky; j++){ //cout << "podmienka" << endl; int zac = 1; int kon = 2; int pocet = 0; cin >> smer >> op >> dlzka; if(smer == "gt"){ if(op == "avg"){ while(kon <= NN){ while(true){ if(mapovanie[zac] >= mapovanie[kon] - dlzka) break; zac++; } int sum = get_sums(zac, kon - 1); //double x = (double)sum / (double)(kon - zac + 1); if(zac < kon && seq[kon] * (kon - zac) > sum) pocet++; kon++; } } else if(op == "min"){ while(kon <= NN){ while(true){ if(mapovanie[zac] >= mapovanie[kon] - dlzka) break; zac++; } int sum = get_sumsMin(zac, kon - 1); //double x = (double)sum / (double)(kon - zac + 1); if(zac < kon && seq[kon] > sum) pocet++; kon++; } } else if(op == "max"){ while(kon <= NN){ while(true){ if(mapovanie[zac] >= mapovanie[kon] - dlzka) break; zac++; } int sum = get_sumsMax(zac, kon -1 ); //double x = (double)sum / (double)(kon - zac + 1); if(zac < kon && seq[kon] > sum) pocet++; kon++; } } } else if(smer == "lt"){ if(op == "avg"){ while(kon <= NN){ while(true){ if(mapovanie[zac] >= mapovanie[kon] - dlzka) break; zac++; } int sum = get_sums(zac, kon - 1); //double x = (double)sum / (double)(kon - zac + 1); if(zac < kon && seq[kon] * (kon - zac) < sum) pocet++; kon++; } } else if(op == "min"){ while(kon <= NN){ while(true){ if(mapovanie[zac] >= mapovanie[kon] - dlzka) break; zac++; } int sum = get_sumsMin(zac, kon - 1); //double x = (double)sum / (double)(kon - zac + 1); if(zac < kon && seq[kon] < sum) pocet++; kon++; } } else if(op == "max"){ while(kon <= NN){ while(true){ if(mapovanie[zac] >= mapovanie[kon] - dlzka) break; zac++; } int sum = get_sumsMax(zac, kon - 1); //double x = (double)sum / (double)(kon - zac + 1); if(zac < kon && seq[kon] < sum) pocet++; kon++; } } } cout << pocet << endl; } } /* N = 3; //seq[0] = 2; seq[1] = 3; seq[2] = 8; seq[3] = 5; inicMax(); cout << N; for (int i = 0; i < N*2; ++i) cout << i << ": " << treeMax[i] << endl; cout << get_sumsMax(2, 3) << endl ; */ }