fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. #include <stack>
  5. #include <queue>
  6. #include <list>
  7. #include <cstring>
  8. #include <string.h>
  9. #include <cmath>
  10. #include <string>
  11. #include <sstream>
  12. #include <cctype>
  13. #include <iomanip>
  14.  
  15. using namespace std;
  16.  
  17. typedef long long ll;
  18.  
  19. const int N = 1e5 + 5;
  20. // Mang tien to
  21. ll prefixSum[N]; 
  22. // deque luu cac gia tri co the thoa truy vanvan
  23. deque<pair<ll, int>> arr; 
  24.  
  25. // Xac dinh phan tu duoc themthem
  26. bool flag;
  27.  
  28. // Chi so hien tai
  29. int cur = 0;
  30. // Chi so bat daudau
  31. int idxDelete = 0;
  32.  
  33. void insertValue(int x)
  34. {
  35.     // Neu phan tu duoc them la am thi danh dau lai
  36.     if (x < 0) {
  37.         flag = false;
  38.     }
  39.     else {
  40.         flag = true;
  41.     }
  42.     prefixSum[cur + 1] = prefixSum[cur] + x;
  43.     // Duy tri 1 mang giam dan
  44.     while (!arr.empty() && arr.back().first <= prefixSum[cur + 1]) {
  45.         arr.pop_back();
  46.     }
  47.     // Them vao mang phan tu do
  48.     arr.emplace_back(prefixSum[cur + 1], cur + 1);
  49.     ++cur;
  50. }
  51.  
  52. void deleteFromFront() {
  53.     // Moi la xoa chi xoa 1 phan tu
  54.     if (arr.front().second == idxDelete) {
  55.         arr.pop_front();
  56.     }
  57.     // Tang chi so bat dau len
  58.     ++idxDelete;
  59. }
  60.  
  61. int findLongestNonNegativeSuffix()
  62. {
  63.     // Neu phan tu am thi khong ton tai mang thoa mang -> Tra ve 0
  64.     if (!flag) {
  65.         return 0;
  66.     }
  67.     // So phan tu cua mang luon >= 1
  68.     // Neu bang 1 thi khong the mo rong them ve phia ben trai -> Tra ve chieu dai mang
  69.     if (arr.size() == 1) {
  70.         return arr.back().second - idxDelete;
  71.     }
  72.     int size = arr.size();
  73.     // Tra ve chieu dai ma trong mang nam o ben trai gan nhat cua mang
  74.     return cur - arr[size - 2].second - 1;
  75. }
  76.  
  77. int main()
  78. {
  79.     ios::sync_with_stdio(false);
  80.     cin.tie(nullptr);
  81.  
  82.     // freopen("input.txt", "r", stdin);
  83.     // freopen("output.txt", "w", stdout);
  84.  
  85.     // Khoi tao
  86.     prefixSum[0] = 0;
  87.     arr.emplace_back(0, 0); 
  88.  
  89.     int q;
  90.     cin >> q;
  91.  
  92.     for (int i = 0; i < q; i++) {
  93.         int op;
  94.         cin >> op;
  95.  
  96.         if (op == 1) {
  97.             int x;
  98.             cin >> x;
  99.             insertValue(x);
  100.         }
  101.         else if (op == 2) {
  102.             deleteFromFront();
  103.         }
  104.         else if (op == 3) {
  105.             int ans = findLongestNonNegativeSuffix();
  106.             cout << ans << '\n';
  107.         }
  108.     }
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/gwbseB
language:
C++14 (gcc 8.3)
created:
7 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!