fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. void fastio();
  4. #define ll long long
  5. #define all(x) x.begin(), x.end()
  6. const int MOD = 1e9 + 7;
  7.  
  8. // Custom I/O operators
  9. template <typename A, typename B>
  10. ostream& operator<<(ostream& out, const pair<A, B>& p) {
  11.         return out << p.first << ' ' << p.second;
  12. }
  13. template <typename A, size_t n>
  14. ostream& operator<<(ostream& out, const array<A, n>& v) {
  15.         for (int i = 0; i < int(n) - 1; ++i) out << v[i] << ' ';
  16.         return (n ? out << v.back() : out << '\n');
  17. }
  18. template <typename A>
  19. ostream& operator<<(ostream& out, const vector<A>& v) {
  20.         for (int i = 0; i < int(v.size()) - 1; ++i) out << v[i] << ' ';
  21.         return (v.size() ? out << v.back() : out << '\n');
  22. }
  23. template <typename A, typename B>
  24. istream& operator>>(istream& in, pair<A, B>& p) {
  25.         in >> p.first;
  26.         return in >> p.second;
  27. }
  28. template <typename A, size_t n>
  29. istream& operator>>(istream& in, array<A, n>& v) {
  30.         for (int i = 0; i < n; i++) in >> v[i];
  31.         return in;
  32. }
  33. template <typename A>
  34. istream& operator>>(istream& in, vector<A>& v) {
  35.         for (int i = 0; i < v.size(); i++) in >> v[i];
  36.         return in;
  37. }
  38.  
  39. #include <ext/pb_ds/assoc_container.hpp>
  40. #include <ext/pb_ds/tree_policy.hpp>
  41.  
  42. using namespace __gnu_pbds;
  43.  
  44. #define ordered_multiset \
  45.         tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update>
  46.  
  47. void solve() {
  48.         ll n;
  49.         cin >> n;
  50.         vector<ll> v(n);
  51.         cin >> v;
  52.         ll q;
  53.         cin >> q;
  54.         ordered_multiset ms;
  55.         map<pair<ll, ll>, ll> mpp;
  56.         vector<tuple<ll, ll, ll>> qry(q);
  57.         vector<pair<ll, ll>> vp;
  58.         for (int i = 0; i < q; ++i) {
  59.                 ll a, b, c;
  60.                 cin >> a >> b >> c;
  61.                 qry[i] = {a, b, c};
  62.                 vp.push_back({a - 1, c});
  63.                 vp.push_back({b, c});
  64.         }
  65.  
  66.         sort(all(vp));
  67.         reverse(all(vp));
  68.         ll j = 0;
  69.         while (!vp.empty()) {
  70.                 auto [cnt, k] = vp.back();
  71.                 vp.pop_back();
  72.                 while (ms.size() < cnt) {
  73.                         ms.insert(v[j]);
  74.                         j++;
  75.                 }
  76.                 if (cnt == 0) {
  77.                         mpp[{cnt, k}] = 0;
  78.                         continue;
  79.                 }
  80.                 if(mpp.count({cnt,k})) continue;
  81.                 ll x = cnt - ms.order_of_key(k + 1);
  82.                 mpp[{cnt, k}] = x;
  83.         }
  84.         for (int i = 0; i < q; ++i) {
  85.                 auto [a, b, c] = qry[i];
  86.                 cout << mpp[{b, c}] - mpp[{a - 1, c}] << endl;
  87.         }
  88. }
  89.  
  90. int main() {
  91.         fastio();
  92.  
  93.         int t = 1;
  94.         while (t--) {
  95.                 solve();
  96.                 cout << '\n';
  97.         }
  98.         return 0;
  99. }
  100.  
  101. void fastio() {
  102.         ios::sync_with_stdio(false);
  103.         cin.tie(NULL);
  104.  
  105. #ifndef ONLINE_JUDGE
  106.         freopen("input.txt", "r", stdin);
  107.         freopen("output.txt", "w", stdout);
  108. #endif
  109. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
 3
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/eLnUDQ
					
					
					
					
					

												
problem KQUERY, based on SPOJ submission 35301232 (CPP14), 2025-12-04 18:30:01

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
1 day 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!