fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. #define all(x) x.begin(), x.end()
  6. #define sz(x) (int)x.size()
  7. #define pb push_back
  8. #define re exit(0);
  9. #define FOR(i, a, b)   for(int i = (a), _b = (b); i <= _b; i++)
  10. #define FORD(i, a, b)  for(int i = (a), _b = (b); i >= _b; i--)
  11. #define LOOP(a)        for(int i = 0, _a = (a); i < _a; i++)
  12.  
  13. using namespace std;
  14.  
  15. typedef vector<int> vi;
  16. typedef pair<int, int> pii;
  17. typedef vector<pii> vii;
  18.  
  19. template<typename T> void chkmin(T &x, T y) {if (y < x) x = y;}
  20. template<typename T> void chkmax(T &x, T y) {if (y > x) x = y;}
  21.  
  22. const int mod = 1e9 + 7;
  23. void add(int &a, int b) {
  24.     a += b;
  25.     if (a >= mod) a -= mod;
  26.     if (a < 0) a += mod;
  27. }
  28.  
  29. int _pow(int a, int b) {
  30.    int ans = 1;
  31.    while (b) {
  32.    if (b % 2 == 1) ans = 1ll * ans * a % mod;
  33.         a = 1ll * a * a % mod;
  34.         b /= 2;
  35.    }
  36.    return ans;
  37. }
  38. void rf() {
  39.    freopen("input.inp", "r", stdin);
  40. }
  41.  
  42. //--------------------------------------------------------------------------------------------------------------------------------------
  43.  
  44. struct hihi {
  45.     int type, l, r, x, id;
  46. };
  47.  
  48. const int maxn = 1e5;
  49. int a[maxn + 5];
  50. int n, numQuery;
  51. int sqrt_n;
  52.  
  53. bitset<maxn> s1, s2;
  54. int cnt[maxn + 5];
  55. int ans[maxn + 5];
  56. vector<hihi> queries;
  57.  
  58. bool cmp(hihi a, hihi b) {
  59.     int block_a = a.l / sqrt_n, block_b = b.l / sqrt_n;
  60.     if (block_a != block_b) return block_a < block_b;
  61.     return a.r < b.r;
  62. }
  63.  
  64. void push(int val) {
  65.     cnt[val]++;
  66.     if (cnt[val] == 1) {
  67.         s1[val] = 1;
  68.         s2[maxn - val] = 1;
  69.     }
  70. }
  71. void pop(int val) {
  72.     cnt[val]--;
  73.     if (cnt[val] == 0) {
  74.         s1[val] = 0;
  75.         s2[maxn - val] = 0;
  76.     }
  77. }
  78.  
  79. int main() {
  80.     ios::sync_with_stdio(0);
  81.     cin.tie(0);
  82.  
  83. //    rf();
  84.  
  85.     cin >> n >> numQuery;
  86.  
  87.     for (int i = 1; i <= n; i++)
  88.         cin >> a[i];
  89.     sqrt_n = sqrt(n);
  90.  
  91.     for (int i = 1; i <= numQuery; i++) {
  92.         int type, l, r, x;
  93.         cin >> type >> l >> r >> x;
  94.         queries.push_back({type, l, r, x, i});
  95.     }
  96.     sort(all(queries), cmp);
  97.  
  98.     int L = 1, R = 0;
  99.     for (hihi query : queries) {
  100.         while (L < query.l) pop (a[L++]);
  101.         while (L > query.l) push(a[--L]);
  102.         while (R < query.r) push(a[++R]);
  103.         while (R > query.r) pop (a[R--]);
  104.  
  105.         int x = query.x;
  106.  
  107.         if (query.type == 1)
  108.             ans[query.id] = (s1 & (s1 << x)).any();
  109.         else if (query.type == 2)
  110.             ans[query.id] = (s2 & (s1 << (maxn - x))).any();
  111.         else if (query.type == 3) {
  112.             for (int i = 1; i * i <= x; i++) {
  113.                 if (x % i == 0 && s1[i] && s1[x / i]) {
  114.                     ans[query.id] = 1;
  115.                     break;
  116.                 }
  117.             }
  118.         }
  119.     }
  120.  
  121.     for (int i = 1; i <= numQuery; i++)
  122.         cout << (ans[i] ? "hana\n" : "bi\n");
  123.  
  124.     return 0;
  125. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/7ckuS4
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!