fork download
copy 
  1. // solstice 
  2. // created at 9 february 2025 
  3. // sussy baka
  4. /*
  5. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠖⠀⠀⢀⣨⣤⡤⠶⠶⠶⠶⢦⣤⣤⣀⠐⠢⢤⣀⠀⠀⠀⠀⠀⠀⠀⡆⣿⠀⠀⣀⠈⢷⡘⣷⠀⠀⠀⠀⠀
  6. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡴⠚⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠓⠦⣌⡙⠶⣄⠀⠀⠀⢠⠀⣿⠀⢠⡇⠀⠈⡇⢸⠀⠀⠀⠀⠀
  7. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠶⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠷⣌⠻⣦⣠⠏⣸⠃⢀⣎⡇⠀⢠⡇⣼⠀⠀⠀⠀⠀
  8. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⢀⡴⠶⣄⠀⠀⠀⠀⠈⠳⣌⡙⢰⠇⢀⣾⠟⠛⢳⡼⢁⠋⠀⠀⠀⠀⠀
  9. ⠀⠰⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⡏⠀⠀⠀⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⠙⠻⢤⣀⣈⣷⡚⠛⠲⠦⣄⣨⣿⡟⢠⡿⠁⢀⣴⠟⢡⠎⠀⠀⠀⠀⠀⠀
  10. ⠀⠀⠹⡏⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣼⣧⡀⠀⠀⠀⠉⠉⠳⣄⠀⠈⠙⣿⢁⣿⣥⣶⡟⢁⣠⡤⠔⠒⠒⠒⠒⠀⠀
  11. ⠀⠀⠀⢻⣦⡀⣀⡀⠀⠀⠀⠀⠀⣠⡴⠛⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣿⣏⡁⢎⠻⠶⣦⣄⠀⠀⠀⠈⣧⠀⠀⣿⣼⡿⣿⣿⠟⠋⢁⣀⠀⠀⠀⠀⠀⠀⣀
  12. ⠀⠀⠀⠀⢿⡁⠉⠉⠉⠁⢀⣴⠞⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣟⣛⡛⠉⣿⡻⢷⣶⣾⡶⣿⢷⡄⠀⠀⢸⡷⣦⣸⣿⣿⣶⣿⣶⣾⣿⣦⠀⢀⣀⡤⠖⠋⠁
  13. ⠀⠀⠀⠀⠈⢷⡀⠀⠀⢠⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⣿⣶⣿⣷⣄⠙⢯⡉⠙⠛⠛⢦⣄⡋⢛⠀⢻⠋⣠⡟⢸⣿⣋⣀⣼⣶⡟⢥⡖⠋⠁⠀
  14. ⠀⠀⠀⠀⠀⠈⡇⠀⠀⣿⠋⢻⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⡾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠙⠒⠒⠒⠂⠻⣿⣺⠀⣼⠟⠉⢀⣼⣿⣿⣿⣿⣙⢿⡌⢷⡀⠀⠀
  15. ⠀⠀⠀⠀⠀⠀⣇⠀⠀⢸⣦⣌⣻⣷⣤⣄⣀⠀⠀⣀⣤⣶⣾⣿⣿⣿⣶⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣏⣹⣿⣦⡀⠀⢀⣤⡴⠛⢿⡞⠃⠀⢠⣾⣧⣅⡀⠸⣿⣿⣾⢳⡄⢳⣄⠀
  16. ⠀⠀⠀⠀⠀⠀⠙⠷⣤⣄⣉⠻⠿⣶⣤⣭⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⠏⢀⡴⠿⠿⢶⣾⣋⠁⠀⠈⢳⣄⣿⣿⣿⣧⣿⡆⢸⢠
  17. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢨⡿⣠⣿ ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠀⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢁⡴⠛⠃⣀⠀⠀⠙⡇⢀⣀⣀⣈⣿⣿⣿⣿⣿⣿⠇⣼⣻
  18. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠞⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠗⠶⠦⢼⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣾⣿⣿⣿⣿⣿⣷⣤⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢁⡼⣹⣿
  19. ⣤⣤⡀⠀⠀⢀⣤⣴⠞⠋⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠺⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠁⠀⠈⣸⣿⣿
  20. ⣿⣿⣿⣷⠞⢉⡽⠁⠀⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣿⠏⠀⢀⣠⣤⣤⣀⠉⢪⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡅⠀⠀⠀⠀⣿⣿⣿
  21. ⣿⠿⠋⠀⢀⠞⠀⠀⠀⢠⣾⣿⣿⣿⣿⣿⣿⠟⣹⣥⡀⣰⣿⡿⠁⠀⠀⢩⣾⣿⣿⡙⠿⣦⣍⠈⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⢻⡿⢸
  22. ⠀⠀⠀⢠⠏⠀⠠⠤⠾⠿⠛⣿⣿⣿⣿⣿⣿⣰⣟⣿⣾⠟⠉⠀⠀⠀⠀⠀⣿⣟⣿⡟⠓⠺⢿⣿⠦⠞⣿⣿⣿⣿⣿⣿⣿⡟⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠀⠀⠀⠀⠈⠃⠘
  23. ⠀⠀⢠⠏⠀⠀⠀⣠⠶⠆⢸⡿⢻⣿⣿⣿⣿⣿⡟⣿⣟⠀⠀⠀⠀⠀⠀⠀⠹⣿⣻⡟⣀⡀⠚⠁⠀⠀⣿⣿⣿⣿⣿⣿⣯⣤⡈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⢀⣀⠀
  24. ⠀⢠⠏⠀⠀⣠⠞⠁⠀⠀⢸⡇⠀⢻⣿⣿⣿⣧⠁⣻⣿⣷⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠀⠀⠀⠀⢀⣿⠃⢹⣿⣿⣿⣡⣾⡇⢸⣿⣿⣿⣿⣿⣿⣿⡿⣿⣧⡀⠀⠀⠀⣾⣿⣿
  25. ⢀⠏⢀⡠⠞⠉⠀⠀⠀⠀⠘⠃⠁⢸⣿⣿⣿⣿⠀⠉⣹⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⣁⢠⣾⣿⣿⣿⣿⠛⣰⣿⣿⣿⣿⣿⣿⣿⣿⠁⠈⠉⠛⠒⢀⣴⣿⣿⣿
  26. ⢞⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠚⣱⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⠟⣿⠁⠀⠀⠀⠀⠁⣸⣿⣿⣿⣿
  27. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠿⠛⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⠟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢃⣤⣘⠇⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿
  28. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠋⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣿⠙⠛⠛⠻⠛⣀⣽⡿⣿⢿⣿⠿
  29. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⠙⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⠟⠀⠀⣠⣾⣿⣿⣿⡟⠙⣿⣿⣿⠻⣿⣷⠸⠿⠶⠶⠶⣦⣄⠁⠂⠀⠀⠀⠀⠀
  30. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡟⣿⣿⣧⠀⠻⣄⠀⠀⠀⠀⠀⠀⠀⢀⣠⡴⠏⠁⠀⠀⢀⢿⣿⣿⣿⣿⠇⠀⢹⣿⢿⣶⣾⣿⡶⠖⠒⠒⠲⣆⢻⣆⠀⠀⠀⠀⠀⠀
  31. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⠁⠀⠀⠘⣦⡀⠀⢀⣀⣴⣾⠿⣅⠀⠀⠀⠀⠀⠀⣸⣿⣿⣟⠁⢀⣀⣠⣿⡿⠟⠋⠁⠀⠀⠀⠀⠀⠹⣆⠻⣦⡀⠀⠀⠀⠀
  32. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠟⢻⣿⢻⡄⠀⠀⠀⠈⣙⣛⣻⣭⣴⠶⡛⢿⡆⠀⠀⠀⢀⣼⡿⢿⣿⣿⣟⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠳⣬⡙⠂⠀⠀⠀
  33. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣧⣸⣧⣿⡥⠖⠒⠋⠉⠉⣡⣾⠏⣡⣤⣯⣿⣿⣤⣶⣾⡿⣿⣿⣞⣿⣿⣿⠏⠀⠀⠀⢀⣀⣀⣀⣀⣀⣀⣀⣀⣀⣀⣀⡈⠙⠓⠲⢦⠀
  34. ⠀⠀⠀⠀⠀⠀⠀⠘⠶⣶⢤⠤⠤⠤⣶⣾⢿⣿⡇⠀⠀⠀⠀⢀⣾⠟⠀⠀⣿⣿⠿⢿⡿⠚⠋⢹⠀⣿⡇⣿⡟⢉⣟⣠⣤⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣭⣉⣀⠀⠈⢠
  35. ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠓⠲⠾⢿⣀⣼⣿⠧⣶⣶⣶⣿⣿⣿⡀⠀⢠⣿⡏⠀⢸⡇⠀⠀⢸⡆⢻⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⠆⣼
  36. ⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⣠⣄⡀⣹⠟⣠⡾⠛⣻⣿⣿⣿⣿⣿⣀⣼⠏⠀⠀⣾⠀⠀⠀⢸⣇⣼⣿⣿⣯⠄⡌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⡿⣿⠃⣼⣿
  37. ⠀⠀⠀⠀⠀⠀⠀⠀⠸⣧⣀⣠⣿⡙⣛⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⠀⣼⣧⣤⣶⣿⣿⣿⣿⣿⣿⡇⣀⣰⣞⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⣸⣿⣿
  38. */
  39. #pragma GCC optimize("O3,Ofast,inline")
  40.  
  41. #include <bits/stdc++.h>
  42. #include <ext/pb_ds/assoc_container.hpp>
  43. #include <ext/pb_ds/tree_policy.hpp>
  44. using namespace std;
  45. using namespace __gnu_pbds;
  46.  
  47. typedef long long ll;
  48. #define ld long double
  49. using vi = vector<int>;
  50. #define vl vector<ll>
  51. #define vb vector<bool>
  52. #define vvi vector<vector<int>>
  53. #define vvl vector<vector<ll>>
  54. #define el '\n'
  55. #define pb push_back
  56. #define mp make_pair
  57. #define pii pair<int,int>
  58. #define fi first
  59. #define se second
  60. #define all(v) v.begin(), v.end()
  61. #define allr(v) v.rbegin(), v.rend()
  62. #define trav(a,x) for (auto& a : x)
  63.  
  64. //template<class T> using pq = priority_queue<T>;
  65. template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
  66. template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
  67.  
  68. template<typename T, typename V> 
  69. void __print(const pair<T, V> &x);
  70. template<typename T>
  71. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
  72. template<typename T, typename V>
  73. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
  74. void _print() {cerr << "]\n";}
  75. template <typename T, typename... V>
  76. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  77.  
  78. #define sz(x) (int)(x).size()
  79. #define lb lower_bound 
  80. #define ub upper_bound
  81. //#define int long long
  82. //const int mod=1e9+7
  83. const int mod=998244353;
  84.  
  85. #define pi M_PI
  86.  
  87. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  88.  
  89. // 1indexing:)
  90. const int maxc=1002;
  91.  
  92. /*
  93. make prefix sum 2d, dulu pernah ngerjain soal ginian di cf pas mindstorming deng lupa gw kapan
  94. */
  95. int ps[maxc][maxc];
  96.  
  97. void venti(){
  98. 	int n,m; cin >> n >>m;
  99.  
  100. 	vector<pii> orang(n+1);
  101. 	vvi grid(maxc,vi(maxc,0));
  102.  
  103. 	for(int i = 1;i<=n;i++){
  104. 		int x,y; cin >> x>> y;
  105. 		orang[i] ={x,y};
  106. 		grid[x][y]=1;
  107. 	}
  108.  
  109. 	for (int i=1;i<maxc;i++){
  110. 		for (int j=1;j<maxc;j++)ps[i][j]=grid[i][j]+ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1];
  111. 	}
  112.  
  113.  
  114. 	vvi hl(maxc),hr(maxc);
  115. 	vvi v(maxc),vt(maxc);
  116.  
  117. 	for(int i  =0;i<m;i++){
  118. 		int u,vv;cin>>u>>vv;
  119. 		int x1=orang[u].fi,y1=orang[u].se;
  120. 		int x2=orang[vv].fi,y2=orang[vv].se;
  121. 		if(y1==y2){
  122. 			int row=y1;
  123. 			int l=min(x1,x2),r=max(x1,x2);
  124. 			hl[row].pb(l); hr[row].pb(r);
  125. 		}else if(x1==x2){
  126. 			int col=x1;
  127. 			int b=min(y1,y2),t=max(y1,y2);
  128. 			vt[col].pb(t); v[col].pb(b);
  129. 		}
  130. 	}
  131.  
  132. 	for(int y=1;y<maxc;y++){
  133. 		if(!hl[y].empty()){
  134. 			int ss=sz(hl[y]);
  135. 			vector<pii> edge(ss);
  136. 			for(int i =0;i<ss;i++)edge[i]={hl[y][i],hr[y][i]};
  137. 			sort(all(edge));
  138. 			hl[y].resize(ss);hr[y].resize(ss);
  139. 			for(int i=0;i<ss;i++){
  140. 				hl[y][i]=edge[i].fi; hr[y][i]=edge[i].se;
  141. 			}
  142. 		}
  143. 	}
  144.  
  145. 	for(int x=1;x<maxc;x++){
  146. 		if(!v.empty()){
  147. 			int ss=sz(v[x]);
  148. 			vector<pii> edge(ss);
  149. 			for(int i =0;i<ss;i++)edge[i]={v[x][i],vt[x][i]};
  150. 			sort(all(edge));
  151. 			v[x].resize(ss);vt[x].resize(ss);
  152. 			for(int i=0;i<ss;i++){
  153. 				v[x][i]=edge[i].fi; vt[x][i]=edge[i].se;
  154. 			}
  155. 		}
  156. 	}
  157.  
  158. 	int q; cin >>q;
  159. 	while(q--){
  160. 		int x1,x2,y1,y2; cin >> x1 >> y1 >> x2 >> y2;
  161.  
  162. 		int cnt=ps[x2][y2]-ps[x1-1][y2]-ps[x2][y1-1]+ps[x1-1][y1-1];
  163.  
  164. 		int hor=0;
  165. 		for(int y=y1;y<=y2;y++){
  166. 			if(hl[y].empty()) continue;
  167. 			int idx=lb(all(hl[y]),x1)-hl[y].begin();
  168. 			//ascended
  169. 			if(idx==sz(hl[y]))continue;
  170. 			int pos=lb(hr[y].begin()+idx,hr[y].end(),x2+1)-hr[y].begin();
  171. 			hor+=pos-idx;
  172. 		}
  173.  
  174. 		int vert=0;
  175. 		for(int x=x1;x<=x2;x++){
  176. 			if(v[x].empty()) continue;
  177. 			int idx=lb(all(v[x]),y1)-v[x].begin();
  178. 			//ascended
  179. 			if(idx==sz(v[x]))continue;
  180. 			int pos=lb(vt[x].begin()+idx,vt[x].end(),y2+1)-vt[x].begin();
  181. 			hor+=pos-idx;
  182. 		}
  183.  
  184. 		// vertices and edge
  185. 		cout<<cnt-(hor+vert)<<el;
  186.  
  187. 	}
  188. }
  189.  
  190. int main(){
  191. 	cin.tie(0)->sync_with_stdio(0);
  192. 	venti();
  193. 	return 0;
  194. }
Success #stdin #stdout 0.01s 11188KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/f6333f
language:
C++14 (gcc 8.3)
created:
8 days 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!