fork download 
  1. #include "bits/stdc++.h"
  2. #define int long long 
  3.  
  4. using namespace std;
  5.  
  6. int T;
  7.  
  8. int n;
  9. int a[200111];
  10.  
  11. int sum[200111];
  12. int minLeft[200111];
  13. int maxLeft[200111];
  14.  
  15. int getSum(int L, int R)
  16.     {
  17.         return sum[R] - sum[L - 1];
  18.     }
  19.  
  20. int getMax(int L, int R)
  21.     {
  22.         sum[L - 1] = 0;
  23.         for(int i = L; i <= R; i++) { sum[i] = sum[i-1] + a[i]; }
  24.  
  25.         minLeft[L - 1] = 0;
  26.         for(int i = L; i <= R; i++) { minLeft[i] = min(minLeft[i-1], sum[i]); }
  27.  
  28.         int ans = 0;
  29.         for(int i = L; i <= R; i++) { ans = max(ans, sum[i] - minLeft[i]); }
  30.  
  31.         return ans;
  32.     }
  33.  
  34. int getMin(int L, int R)
  35.     {
  36.         sum[L - 1] = 0;
  37.         for(int i = L; i <= R; i++) { sum[i] = sum[i-1] + a[i]; }
  38.  
  39.         maxLeft[L - 1] = 0;
  40.         for(int i = L; i <= R; i++) { maxLeft[i] = max(maxLeft[i-1], sum[i]); }
  41.  
  42.         int ans = 0;
  43.         for(int i = L; i <= R; i++) { ans = min(ans, sum[i] - maxLeft[i]); }
  44.  
  45.         return ans;
  46.     }
  47.  
  48. void solve()
  49.     {
  50.         cin >> n;
  51.         for(int i = 1; i <= n; i++) { cin >> a[i]; }
  52.  
  53.         set<int> res;
  54.  
  55.         int pos = -1;
  56.         for(int i = 1; i <= n; i++)
  57.             {
  58.                 if ((a[i] != -1) && (a[i] != 1)) { pos = i; }
  59.             }
  60.  
  61.         if (pos == -1)
  62.             {
  63.                 int p = getMin(1, n);
  64.                 int q = getMax(1, n);
  65.                 for(int i = p; i <= q; i++) { res.insert(i); }
  66.             }
  67.         else 
  68.             {
  69.                 int p = getMin(1, pos - 1);
  70.                 int q = getMax(1, pos - 1);
  71.                 for(int i = p; i <= q; i++) { res.insert(i); }
  72.  
  73.                 p = getMin(pos + 1, n);
  74.                 q = getMax(pos + 1, n);
  75.                 for(int i = p; i <= q; i++) { res.insert(i); }
  76.  
  77.                 sum[0] = 0;
  78.                 for(int i = 1; i <= n; i++) { sum[i] = sum[i-1] + a[i]; }
  79.  
  80.                 int minL = 0, minR = 0;
  81.                 for(int i = pos - 1; i >= 1; i--) { minL = min(minL, getSum(i, pos - 1)); }
  82.                 for(int i = pos + 1; i <= n; i++) { minR = min(minR, getSum(pos + 1, i)); }
  83.  
  84.                 int maxL = 0, maxR = 0;
  85.                 for(int i = pos - 1; i >= 1; i--) { maxL = max(maxL, getSum(i, pos - 1)); }
  86.                 for(int i = pos + 1; i <= n; i++) { maxR = max(maxR, getSum(pos + 1, i)); }
  87.  
  88.                 for(int i = a[pos] + minL + minR; i <= a[pos] + maxL + maxR; i++) { res.insert(i); }
  89.             }
  90.  
  91.         cout << res.size() << '\n';
  92.         for(int i : res) { cout << i << " "; }
  93.         cout << '\n';
  94.     }
  95.  
  96. int32_t main()
  97. {
  98.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  99.  
  100.     cin >> T;
  101.  
  102.     while (T--) { solve(); }
  103.  
  104.     return 0;
  105. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/VB7UCy
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!