fork download
copy 
  1. #include <bits/stdc++.h>
  2. signed main() {
  3.     int n;
  4.     std::cin >> n;
  5.     int a[n];
  6.     long long p[n], s[n+1];
  7.     for (int i=0; i<n; ++i) {
  8.         std::cin >> a[i];
  9.         p[i] = s[i] = a[i];
  10.         if (i) p[i] += p[i-1];
  11.     }
  12.     s[n] = 0;
  13.     for (int i=n-2; ~i; --i)
  14.         s[i] += s[i+1];
  15.     std::vector<std::pair<long long, std::pair<int, int>>> ans;
  16.     ans.push_back({0, {0, n-1}});
  17.     for (int i=1; 2*i<n; ++i) {
  18.         int j = n - i;
  19.         ans.push_back({p[i-1] + s[j+1], {i, j}});
  20.     }
  21.     for (int i=0; 2*i + 2 < n; ++i) {
  22.         int j = n - i - 2;
  23.         ans.push_back({(i?p[i-1]:0) + s[j+1], {i, j}});
  24.     }
  25.     std::sort(ans.begin(), ans.end());
  26.     std::pair<int, int> mx{0, 0};
  27.     for (int i=0; i<ans.size(); ++i) {
  28.         mx = std::max(mx, ans[i].second);
  29.         ans[i].second = mx;
  30.     }
  31.     int q;
  32.     std::cin >> q;
  33.     while (q--) {
  34.         long long k;
  35.         std::cin >> k;
  36.         auto it = std::upper_bound(ans.begin(), ans.end(), std::make_pair(k+1, std::make_pair(-1, -1)));
  37.         --it;
  38.         std::cout << it->second.first + 1 << ' ' << it->second.second + 1 << '\n';
  39.     }
  40. }
Success #stdin #stdout 0.01s 5228KB
comments (?)
stdin
copy 
5
2 5 1 10 3
3
2
20
1
stdout
copy 
2 5
3 4
1 5
https://ideone.com/aQAn0W
language:
C++14 (gcc 8.3)
created:
1 day 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!