fork download
copy 
  1. /// Author: Nguyen Thanh Phong  -  ti25phong_nt
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define el cout << "\n";
  6. #define FOR(i, start, end, step) for(int i=start; i<=end; i+=step)
  7. #define FORD(i, end, start, step) for(int i=end; i>=start; i-=step)
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define pf push_front
  12. #define popb pop_back()
  13. #define popf pop_front()
  14. #define ALL(x) (x).begin(),(x).end()
  15. #define ElfariaAlbisSerfort int main()
  16.  
  17. typedef long long ll;
  18. typedef unsigned long long ull;
  19. typedef vector<int> vi;
  20. typedef vector<ll> vll;
  21. typedef pair<int, int> pii;
  22. typedef pair<ll, ll> pll;
  23.  
  24. const int NN = 1e6 + 5;
  25. const int INF = 0x3f3f3f3f;
  26. const long long LINF = 1e18 + 7;
  27. const int base = 31;
  28. const long long MOD = 1e9 + 7;
  29. const int d4x[] = {0, 0, -1, 1};
  30. const int d4y[] = {-1, 1, 0, 0};
  31. const int d8x[] = {-1, -1, -1, 0, 0, 1, 1, 1};
  32. const int d8y[] = {-1, 0, 1, -1, 1, -1, 0, 1};
  33.  
  34. /// ------------------ GLOBAL VARIABLE ------------------
  35. int n, q;
  36. ll a[NN], pre[NN];
  37.  
  38. /// ------------------ MAIN PROGRAMME -------------------
  39. ElfariaAlbisSerfort
  40. {
  41. #define NAME "jump"
  42.     if(fopen(NAME".inp","r"))
  43.     {
  44.         freopen(NAME".inp", "r", stdin);
  45.         freopen(NAME".out", "w", stdout);
  46.     }
  47.  
  48.     ios_base :: sync_with_stdio(false);
  49.     cin.tie(0);
  50.     cout.tie(0);
  51.  
  52.     cin >> n >> q;
  53.     FOR(i, 1, n, 1)
  54.     {
  55.         cin >> a[i];
  56.         pre[i] = pre[i-1]+a[i];
  57.     }
  58.  
  59.     while(q--)
  60.     {
  61.         int L, R;
  62.         cin >> L >> R;
  63.         deque<int> dq;
  64.         dq.push_back(0);
  65.         int i=0;
  66.         ll ans=-LINF;
  67.         int ansl=0, ansr=0;
  68.         FOR(j, L, n, 1)
  69.         {
  70.             if(pre[j]-pre[dq.front()] > ans)
  71.             {
  72.                 ans = pre[j] - pre[dq.front()];
  73.                 ansl=dq.front()+1;
  74.                 ansr=j;
  75.             }
  76.             i++;
  77.             while(!dq.empty() && j+1-dq.front()>R) dq.pop_front();
  78.             while(!dq.empty() && pre[dq.back()]>=pre[i]) dq.pop_back();
  79.             dq.push_back(i);
  80.         }
  81.         cout << ans << "\n" << ansl << " " << ansr << "\n";
  82.     }
  83.  
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/D2wmWe
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!