fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. template<class T> void ckmin(T &a, T b) { a = min(a, b); }
  4. template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  5. #define pb push_back
  6. #define mp make_pair
  7. #define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  8. #define F first
  9. #define S second
  10. #define sz(x) (int)x.size()
  11. #define all(x) (x).begin(), (x).end()
  12. #define rep(i, n) for(int i = 0; i < n; ++i)
  13. #define repr(i,n) for(int i = n - 1; i >= 0; --i)
  14. #define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
  15. #define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
  16. #define Repr(i, a, n) for(int i = (n); i >= (a); --i)
  17. typedef long long ll;
  18.  
  19. const int inf = int(1e9);
  20. const int mod = 1e9 + 7;
  21. const int N = 1e6 + 555;
  22. const long double PI = acos(-1.0);
  23.  
  24. int t[N], a[N], pos[N];
  25.  
  26. void build(int v, int tl, int tr){
  27. 	if(tl == tr) t[v] = a[tl];
  28. 	else{
  29. 		int tm = tl + tr >> 1;
  30. 		build(2 * v, tl, tm);
  31. 		build(2 * v + 1, tm + 1, tr);
  32. 		t[v] = t[v + v] + t[v + v + 1];
  33. 	}
  34. }
  35. int sum(int v, int tl, int tr, int l, int r){
  36. 	if(tr < l || r < tl) return 0;
  37. 	if(l <= tl && tr <= r) return t[v];
  38. 	int tm = tl + tr >> 1;
  39. 	return sum(2 * v, tl, tm, l, r) + sum(2 * v + 1, tm + 1, tr, l, r); 
  40. }
  41. void solve()
  42. {	
  43. 	int n;
  44. 	cin >> n;
  45. 	vector<pair<int, int> > b;
  46. 	rep(i, n){
  47. 		cin >> a[i];
  48. 		b.pb(mp(a[i], i));
  49. 	}
  50. 	sort(all(b));
  51. 	for(int i = 0; i < n; ++i){
  52. 		pos[i + 1] = b[i].S;
  53. 	}
  54. 	build(1, 0, n - 1);
  55. 	int m;
  56. 	cin >> m;
  57. 	rep(i, m){
  58. 		int x, y;
  59. 		cin >> x >> y;
  60. 		int curSum = sum(1, 0, n - 1, pos[x], min(n - 1, pos[x] + y - 1));
  61. 		if(pos[x] + y - 1 < n) {
  62. 			cout << curSum << endl;
  63. 		}else{
  64. 			int just = pos[x] + y - 1 - n;
  65. 			int took = just / n;
  66. 			int last = just % n;
  67. 			took = sum(1, 0, n - 1, 0, n - 1) * took;
  68. 			last = sum(1, 0, n - 1, 0, last);
  69. 			cout << curSum + took + last << endl;
  70. 		}
  71. 	}
  72. }
  73. int main()
  74. {
  75. 	Red;
  76. 	solve();
  77. 	return 0;
  78. }
Internal error #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7to9IH
language:
C++ (gcc 8.3)
created:
4 years 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!