fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  10. #define getrand(l, r) uniform_int_distribution<long long>(l, r)(rng)
  11.  
  12. const int mod = 1000'000'007;
  13.  
  14. int power(int a, int p) {
  15.     int ans = 1;
  16.     while (p > 0) {
  17.         if (p % 2 == 1) ans = ans * a % mod;
  18.         a = a * a % mod, p /= 2;
  19.     }
  20.     return ans;
  21. }
  22.  
  23. int solve(int h, int v, int t) {
  24.     --h;
  25.     if (t == 0) return v % mod;
  26.  
  27.     int level = __lg(v);
  28.     int o = v - (1LL << level);
  29.     int limit = (1LL << level) - 1;
  30.  
  31.     --t;
  32.     if (o < limit) ++o, ++v;
  33.  
  34.     if (t == 0) return v % mod;
  35.  
  36.     int toEnd = limit - o;
  37.     int d = min(h - level, t / 2);
  38.  
  39.     v = power(2, d) * (v + 1) % mod - 1;
  40.     if (v < 0) v += mod; level += d;
  41.  
  42.     int remain = t - 2 * d;
  43.     if (remain == 0) return v;
  44.  
  45.     if (level < h) return 2 * v % mod;
  46.  
  47.     if (toEnd == 0) return v;
  48.  
  49.     int move = 0, c = remain / 2;
  50.     if (d > 30) {
  51.         move = c;
  52.     } else {
  53.         bint x = (1LL << d), y = toEnd, z = x * y;
  54.         if (c <= z) move = c; else move = z;
  55.     }
  56.     v += move, v %= mod;
  57.  
  58.     return v;
  59. }
  60.  
  61. void getShitDone() {
  62.     int h, q;
  63.     cin >> h >> q;
  64.     while (q--) {
  65.         int v, t;
  66.         cin >> v >> t;
  67.         cout << solve(h, v, t) << '\n';
  68.     }
  69. }
  70.  
  71. signed main() {
  72.     _3bkarm
  73.  
  74.     int ts = 1;
  75. //    cin >> ts;
  76.     while (ts--) getShitDone();
  77.  
  78.     return 0;
  79. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WxuYDU
language:
C++14 (clang 8.0)
created:
4 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!