fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. const int N = 1e5 + 5;
  8. int k, q;
  9. struct query {
  10.     int s, n, l, r, v, id;
  11. } Q[N];
  12. namespace sub1 {
  13. bool checksub() {
  14.     for (int i = 1; i <= q; i++) if (Q[i].n > 5) return 0;
  15.     return 1;
  16. }
  17. void calc(int s, int n, int l, int r, int v) {
  18.     vector<int> cur; cur.push_back(s);
  19.     for (int t = 1; t <= n; t++) {
  20.         vector<int> nxt;
  21.         for (int i: cur) {
  22.             if (i < k) nxt.push_back(i + 1);
  23.             else {
  24.                 for (int i = k; i >= 0; i--) nxt.push_back(i);
  25.                 // nxt.push_back(-1);
  26.             }
  27.         }
  28.         cerr << t<< ": "; for (int i: nxt) cerr << i << " "; cerr << "\n";
  29.         swap(nxt, cur);
  30.     }
  31.     int cnt = 0;
  32.     for (int i = l; i <= r; i++) if (cur[i - 1] == v) cnt++;
  33.     cout << cnt << "\n";
  34. }
  35. void solve() {
  36.     for (int i = 1; i <= q; i++) {
  37.         calc(Q[i].s, Q[i].n, Q[i].l, Q[i].r, Q[i].v);
  38.     }
  39. }
  40. };
  41.  
  42. const int LIM = 1e18;
  43. namespace sub3 {
  44. int fibo[N], sz;
  45. int cnt[N][2];
  46. int getVal(int pos, int layer, int v) {
  47.     if (layer <= 0) return 0;
  48.     if (pos <= 0) return 0;
  49.     if (pos == fibo[layer]) return cnt[layer][v];
  50.     if (pos < fibo[layer - 1]) return getVal(pos, layer - 1, v);
  51.     return getVal(fibo[layer - 1], layer - 1, v) + getVal(pos - fibo[layer - 1], layer - 2, v);
  52. }
  53. void calc(int s, int n, int l, int r, int v) {
  54.     if (n == 0) {
  55.         cout << (s == v) << "\n";
  56.         return;
  57.     }
  58.     if (s == 0) n--;
  59.     cout << getVal(r, min(sz, n + 1), v) - getVal(l - 1, min(sz, n + 1), v) << "\n";
  60. }
  61. void solve() {
  62.     fibo[0] = 1, fibo[1] = 1;
  63.     cnt[0][0] = cnt[1][1] = 1;
  64.     for (int i = 2;; i++) {
  65.         fibo[i] = fibo[i - 1] + fibo[i - 2];
  66.         sz = i;
  67.         cnt[i][0] = cnt[i - 1][0] + cnt[i - 2][0];
  68.         cnt[i][1] = cnt[i - 1][1] + cnt[i - 2][1];
  69.         if (fibo[i] > LIM) break;
  70.     }
  71.     for (int i = 1; i <= q; i++) {
  72.         calc(Q[i].s, Q[i].n, Q[i].l, Q[i].r, Q[i].v);
  73.     }
  74.     // for (int i = 1; i <= sz; i++) {
  75.     //     cerr << i << " " << fibo[i] << " " << cnt[i][0] << " " << cnt[i][1] << "\n";
  76.     // }
  77. }
  78. };
  79. //1100087778366101931 
  80. namespace subfull {
  81. int len[N], sz = 0;
  82. int cnt[N][10];
  83. void build() {
  84.     // memset(cnt, 0, sizeof(cnt));
  85.     for (int i = 0; i <= k; i++) {
  86.         len[i] = 1;
  87.         cnt[i][i] = 1;
  88.         cnt[k + 1][i] = 1;
  89.     }
  90.     len[k + 1] = k + 1;
  91.     int lastNum = 0;
  92.     sz = k + 1;
  93.     for (int i = k + 2;; i++) {
  94.         len[i] = len[i - 1] * 2 - 1;
  95.         for (int j = 0; j <= k; j++) cnt[i][j] = cnt[i - 1][j] * 2;
  96.         cnt[i][lastNum]--;
  97.         if (lastNum < k) lastNum++;
  98.         else lastNum = 0;
  99.  
  100.         sz = i;
  101.         if (len[i] > LIM) break;
  102.     } 
  103.  
  104.  
  105.     // for (int i = 0; i <= sz; i++) {
  106.     //     cerr << i << ": " << len[i] << " | "; for (int j = 0; j <= k; j++) cerr << cnt[i][j] << " "; cerr << "\n";
  107.     // }
  108. }
  109. int getVal(int pos, int layer, int v) {
  110.     if (pos <= k) return (v > k - pos);
  111.  
  112.     if (layer < 0) return 0;
  113.     if (pos == len[layer] || layer == 0) return cnt[layer][v];
  114.     if (pos < len[layer - 1]) return getVal(pos, layer - 1, v);
  115.     return getVal(len[layer - 1], layer - 1, v) + getVal(pos - len[layer - 1], layer - 1, v);
  116. }
  117. void calc(int s, int n, int l, int r, int v) {
  118.     n += s;
  119.     // cerr << n << ": "  << getVal(l - 1, min(sz, n), v) << "  - "<<   getVal(r, min(sz, n), v) << "\n";
  120.     cout << getVal(r, min(sz, n), v) - getVal(l - 1, min(sz, n), v) << "\n";
  121. }
  122. void solve() {
  123.     build();
  124.     for (int i = 1; i <= q; i++) {
  125.         calc(Q[i].s, Q[i].n, Q[i].l, Q[i].r, Q[i].v);
  126.     }
  127. }
  128. };
  129. signed main() {
  130.     cin.tie(NULL)->sync_with_stdio(false);
  131.     if(ifstream("transseq.inp")) {
  132.         freopen("transseq.inp", "r", stdin);
  133.         freopen("transseq.out", "w", stdout);
  134.     }
  135.     cin >> k >> q;
  136.     for (int i = 1; i <= q; i++) {
  137.         cin >> Q[i].s >> Q[i].n >> Q[i].l >> Q[i].r >> Q[i].v;
  138.         Q[i].id = i;
  139.     }
  140.     if (sub1::checksub()) return sub1::solve(), 0;
  141.     if (k == 1) return sub3::solve(), 0;
  142.     return subfull::solve(), 0;
  143.     return 0;
  144. }
  145.  
  146. /*
  147. 1: 1 
  148. 2: 2 
  149. 3: 2 1 0 
  150. 4: 2 1 0 2 1 
  151. 5: 2 1 0 2 1 2 1 0 2 
  152. */
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LmwDNg
language:
C++14 (gcc 8.3)
created:
14 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!