fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int floor_div(int x, int y) {
  4. 	assert(y != 0);
  5. 	if (y < 0) {
  6. 		y = -y;
  7. 		x = -x;
  8. 	}
  9. 	if (x >= 0) return x / y;
  10. 	return (x + 1) / y - 1;
  11. }
  12. int ceil_div(int x, int y) {
  13. 	assert(y != 0);
  14. 	if (y < 0) {
  15. 		y = -y;
  16. 		x = -x;
  17. 	}
  18. 	if (x <= 0) return x / y;
  19. 	return (x - 1) / y + 1;
  20. }
  21. void run_case()
  22. {
  23.     int n ;
  24.     cin>>n;
  25.     vector<vector<int>> pos(100001);
  26.     int mx = 0;
  27.     for(int i = 1 ; i <= n ; i++)
  28.     {
  29.         int x;
  30.         cin>>x;
  31.         pos[x].push_back(i);
  32.         mx = max(mx , x);
  33.     }
  34.     int q;
  35.     cin>>q;
  36.     vector<vector<tuple<int,int,int,int,int ,int>>> adj(100000 + 1);
  37.     vector<int> ans(q);
  38.     vector<int> qux;
  39.     for(int i = 0 ; i < q; i++)
  40.     {
  41.         int x , k , l , r , s , e;
  42.         cin>>x>>k>>l>>r>>s>>e;
  43.         qux.push_back(x);
  44.         adj[x].push_back({k , l , r , s , e , i});
  45.     }
  46.     sort(qux.begin() , qux.end());
  47.     qux.erase(unique(qux.begin() , qux.end()) , qux.end());
  48.     for(auto x : qux)
  49.     {
  50.         vector<int> v;
  51.         for(int y = x ; y <= mx ; y+=x)
  52.         {
  53.             if(!pos[y].empty())
  54.                 v.push_back(y);
  55.         }
  56.         for(auto [k ,l , r , s , e, i] : adj[x])
  57.         {
  58.             int lo = s , hi = e + 2;
  59.             while(lo + 1 < hi)
  60.             {
  61.                 int md = (lo + hi)/2;
  62.                 int nb = 0;
  63.                 for(auto &y : v)
  64.                 {   
  65.                     if(y > r || y < l)
  66.                         continue;
  67.                     nb+= lower_bound(pos[y].begin() , pos[y].end() , md) - lower_bound(pos[y].begin() , pos[y].end() , s);
  68.                 }
  69.                 if(nb < k)
  70.                 {
  71.                     lo = md;
  72.                 }
  73.                 else
  74.                     hi = md;
  75.             }
  76.             ans[i] = (lo <= e ? lo : -1);
  77.         }
  78.     }
  79.     for(int i = 0 ; i < q ; i++)
  80.     {
  81.         cout<<ans[i]<<'\n';
  82.     }
  83. }   
  84. signed main()
  85. {
  86.     ios::sync_with_stdio(0);
  87.     cin.tie(0);
  88.     cout.tie(0);
  89.     int t = 1;
  90.     // cin>>t;
  91.     while(t--)
  92.     {
  93.         run_case();
  94.     }
  95. }
Success #stdin #stdout 0.01s 7776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/60OSVd
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!