fork(1) download
copy 
  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. // số phép đã xóa nhằm xác định chỉ số lúc idx
  20. int idxDelete = 0;
  21. const int N = 1e5 + 5;
  22. // first laf ll, second = int;
  23. // day giam dan
  24. pair<ll, int> arr[N];
  25. // chỉ số hiện tại khi thưcj hiện truy vấn thêm
  26. int cur = 0;
  27. // sum là chỉ số từ 1 tới i
  28. ll prefixSum[N];
  29. int first = 0; // là phần tử dầu của arr
  30. int last = 0; // là phần tử cuối của arr
  31.  
  32. // mang hienj tai
  33. // int a[N];
  34.  
  35. // first la idx, second la value
  36. // queue<pair<int, ll>> q;
  37.  
  38. bool canDelete() {
  39.     return cur > idxDelete;
  40. }
  41.  
  42. // Tra ve idx thoa man
  43. int binarySearch() {
  44.     int l = first;
  45.     int r = last - 1;
  46.     int ans = -1;
  47.     while (l <= r) {
  48.         int mid = (l + r) / 2;
  49.         // thoa man
  50.         // mamg giam dan
  51.         if (arr[mid].first > prefixSum[cur] + prefixSum[idxDelete]) {
  52.             l = mid + 1;
  53.             ans = mid;
  54.         }
  55.         else {
  56.             r = mid - 1;
  57.         }
  58.     }
  59.     return ans;
  60. }
  61.  
  62. void insertValue(int x)
  63. {
  64.     prefixSum[cur + 1] = prefixSum[cur] + x;
  65.     while (first < last && arr[last - 1].first <= prefixSum[cur + 1]) {
  66.         --last;
  67.     }
  68.     arr[last] = {prefixSum[cur + 1], cur + 1};
  69.     ++last;
  70.     ++cur;
  71. }
  72.  
  73. // Hàm xóa số ở đầu dãy
  74. void deleteFromFront()
  75. {
  76.     if (!canDelete()) {
  77.         return;
  78.     }
  79.     if (first < last && arr[first].second == idxDelete + 1) {
  80.         ++first;
  81.     }
  82.     ++idxDelete;
  83. }
  84.  
  85. // Hàm truy vấn độ dài hậu tố dài nhất có tổng không âm
  86. int findLongestNonNegativeSuffix()
  87. {
  88.     int idx = binarySearch();
  89.     if (idx == -1) {
  90.         return idx;
  91.     }
  92.     return cur - arr[idx].second;
  93. }
  94.  
  95. int main()
  96. {
  97.     ios::sync_with_stdio(false);
  98.     cin.tie(nullptr);
  99.  
  100.     int q;
  101.     cin >> q; 
  102.  
  103.     for (int i = 0; i < q; i++)
  104.     {
  105.         int op;
  106.         cin >> op;
  107.  
  108.         if (op == 1)
  109.         {
  110.             int x;
  111.             cin >> x;
  112.             insertValue(x);
  113.         }
  114.         else if (op == 2)
  115.         {
  116.             // TODO: Kiểm tra nếu dãy không rỗng thì mới xóa
  117.             deleteFromFront();
  118.         }
  119.         else if (op == 3)
  120.         {
  121.             int ans = findLongestNonNegativeSuffix(/* TODO: Các tham số cần thiết */);
  122.             cout << ans << "\n";
  123.         }
  124.     }
  125.     return 0;
  126. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rCcE0x
language:
C++14 (gcc 8.3)
created:
12 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!