fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sonic ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0)
  5. #define IO(main) if(fopen(main".inp","r")){freopen(main".inp","r",stdin);freopen(main".out","w",stdout);}
  6. #define pb push_back
  7. #define fi first
  8. #define se second
  9. #define mp make_pair
  10. #define ins insert
  11. #define pb push_back
  12. #define el cout << endl
  13. #define SZ(x) ((int)(x).size())
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define MASK(i) ((1LL)<<(i))
  16. #define BIT(x,i) (((x)>>(i))&(1LL))
  17. #define FOR(i, a, b) for(int (i)=(a);(i)<=(b); i++)
  18. #define FORD(i, a, b) for(int (i)=(a);(i)>=(b); i--)
  19.  
  20.  
  21. using ll = long long;
  22. using ull = unsigned long long;
  23. using ld = long double;
  24.  
  25. using pii = pair<int, int>;
  26. using pll = pair<ll, ll>;
  27. using vi = vector<int>;
  28. using vii = vector<pii>;
  29.  
  30. const int N = 1e5 + 9;
  31. const int mod = 1e9 + 7;
  32. const int INF = 1e9 + 7;
  33. const int base = 31;
  34. const int LOG = 20;
  35.  
  36. template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
  37. template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
  38. void add(int &x, int y) { x += y; if (x>=mod) x-=mod;}
  39. void sub(int &x, int y) { x -= y; if (x<0) x+=mod;}
  40. int mul(int x, int y) {return 1LL * x * y % mod;}
  41. int calPw(int x, int y)
  42. {
  43.     int ans = 1;
  44.     while(y)
  45.     {
  46.         if (y&1) ans = 1LL * ans * x % mod;
  47.         x = 1LL * x * x % mod;
  48.         y >>= 1;
  49.     }
  50.     return ans;
  51. }
  52. int d4x[4] = {1, 0, -1, 0};
  53. int d4y[4] = {0, 1, 0, -1};
  54. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  55. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  56. ///Author: Deruck Phung, Luong The Vinh High School for the Gifted
  57. int n, q, m;
  58. int a[N];
  59. int par[N][40];
  60. //Code
  61. bool check(int l, int r, int v){
  62.     int Ans = 0;
  63.     FORD(i, 30, 0) if(BIT(v, i)) l = par[l][i];
  64.  
  65.     return l >= r;
  66. }
  67.  
  68. void Solve(){
  69.     int iter = 1;
  70.     ll Ans = 0;
  71.     FOR(i, 1, n){
  72.         Ans += a[i];
  73.         while(iter < i && Ans > m){
  74.             Ans -= a[iter];
  75.             iter++;
  76.         }
  77.         par[i][0] = iter - 1;
  78.     }
  79.  
  80.     FOR(i, 1, n) FOR(j, 1, 30){
  81.         par[i][j] = par[par[i][j - 1]][j - 1];
  82.     }
  83.  
  84.     while(q--){
  85.         int u, v;
  86.         cin >> u >> v;
  87.         FORD(i, 30, 0) if(BIT(v, i)){
  88.             u = par[u][i];
  89.         }
  90.  
  91.         cout << u + 1 << "\n";
  92.     }
  93. }
  94.  
  95. void Read(){
  96.     cin >> n >> q >> m;
  97.     FOR(i, 1, n){
  98.         cin >> a[i];
  99.     }
  100. }
  101.  
  102. int main()
  103. {
  104.     sonic;
  105.     IO("main");
  106.     int TEST = 1;
  107.     while(TEST--)
  108.     {
  109.         Read();
  110.         Solve();
  111.     }
  112. }
  113.  
  114.  
  115.  
  116.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7w0MBK
language:
C++14 (gcc 8.3)
created:
30 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!