fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i,a,b) for(int i=a;i<b;i++)
  4. #define REP(i,b) FOR(i,0,b)
  5. #define PB push_back
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. int read(){
  12. 	int i;
  13. 	scanf("%d",&i);
  14. 	return i;
  15. }
  16.  
  17. const int maxN=100000;
  18. const int maxQ=100000;
  19. const int maxX=100001;
  20. const int B=500;
  21. const int D=200;
  22.  
  23. struct Query{
  24. 	int t,l,r,i;
  25. 	bool operator<(const Query& rhs)const{
  26. 		return t<rhs.t;
  27. 	}
  28. } qs[maxQ];
  29.  
  30.  
  31. int x[maxN],v[maxN],sum[maxX],ans[maxQ];
  32. inline void Add(ll i,int a){
  33. 	if(0<=i&&i<maxX)
  34. 		sum[i]+=a;
  35. }
  36. inline int Get(int i){
  37. 	if(i<0)
  38. 		return 0;
  39. 	return sum[min(i,maxX-1)];
  40. }
  41. vector<int> pos[D*2];
  42.  
  43. int main(){
  44. 	int n=read();
  45. 	REP(i,n){
  46. 		x[i]=read(),v[i]=read();
  47. 		sum[x[i]]++;
  48. 		if(abs(v[i])<D)
  49. 			pos[v[i]+D].PB(x[i]);
  50. 	}
  51. 	FOR(i,1,maxX)
  52. 		sum[i]+=sum[i-1];
  53.  
  54. 	int q=read(),s=0;
  55. 	REP(i,q){
  56. 		int t=read(),l=read(),r=read();
  57. 		qs[i]=Query{t,l,r,i};
  58. 		if(t<=B)
  59. 			s++;
  60. 	}
  61. 	sort(qs,qs+q);
  62.  
  63. 	int last=0;
  64. 	REP(i,s){
  65. 		if(qs[i].t>last){
  66. 			memset(sum,0,sizeof(sum));
  67. 			REP(j,n)
  68. 				Add(ll(x[j])+ll(v[j])*qs[i].t,1);
  69. 			FOR(j,1,maxX)
  70. 				sum[j]+=sum[j-1];
  71. 			last=qs[i].t;
  72. 		}
  73. 		ans[qs[i].i]=Get(qs[i].r)-Get(qs[i].l-1);
  74. 	}
  75.  
  76. 	REP(i,D*2){
  77. 		if(pos[i].empty())
  78. 			continue;
  79. 		memset(sum,0,sizeof(sum));
  80. 		for(auto j:pos[i])
  81. 			sum[j]++;
  82. 		FOR(j,1,maxX)
  83. 			sum[j]+=sum[j-1];
  84. 		FOR(j,s,q)
  85. 			ans[qs[j].i]+=Get(qs[j].r-(i-D)*qs[j].t)-Get(qs[j].l-(i-D)*qs[j].t-1);
  86. 	}
  87. 	REP(i,q)
  88. 		printf("%d\n",ans[i]);
  89. }
Runtime error #stdin #stdout 0s 6588KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/HSRWQ0
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!