fork download
copy 
  1. #include <bits/stdc++.h>
  2. #ifndef ONLINE_JUDGE
  3. #include "debug.h"
  4. #else
  5. #define debug(...)
  6. #endif
  7. // #define int long long
  8. #define pep_Guardiola      \
  9.   ios::sync_with_stdio(0); \
  10.   cin.tie(0);              \
  11.   cout.tie(0);
  12. using namespace std;
  13.  
  14. void io()
  15. {
  16. #ifndef ONLINE_JUDGE
  17.   freopen("input.txt", "r", stdin);
  18.   // freopen("output.txt", "w", stdout);
  19. #endif
  20. }
  21.  
  22. void Guardiola()
  23. {
  24.   int n, q;
  25.   cin >> n >> q;
  26.   vector<int> a(n + 1, 0), prefix(n + 1, 0);
  27.   for (int i = 1; i <= n; i++)
  28.   {
  29.     cin >> a[i];
  30.     prefix[i] = prefix[i - 1] + a[i];
  31.   }
  32.   set<int> cuts;
  33.   cuts.insert(1), cuts.insert(n + 1);
  34.   multiset<int> sums;
  35.   sums.insert(prefix[n] - prefix[0]);
  36.   while (q--)
  37.   {
  38.     int type, x;
  39.     cin >> type >> x;
  40.     if (type == 1)
  41.     {
  42.       if (cuts.count(x))
  43.       {
  44.         cout << *sums.rbegin() << '\n';
  45.         continue;
  46.       }
  47.       auto it = cuts.upper_bound(x);
  48.       int r = *it - 1, l = *prev(it);
  49.       sums.erase(sums.find(prefix[r] - prefix[l - 1]));
  50.       sums.insert(prefix[x - 1] - prefix[l - 1]);
  51.       sums.insert(prefix[r] - prefix[x - 1]);
  52.       cuts.insert(x);
  53.     }
  54.     else
  55.     {
  56.       auto it = cuts.find(x);
  57.       int r = *next(it) - 1, l = *prev(it);
  58.       sums.erase(sums.find(prefix[x - 1] - prefix[l - 1]));
  59.       sums.erase(sums.find(prefix[r] - prefix[x - 1]));
  60.       sums.insert(prefix[r] - prefix[l - 1]);
  61.       cuts.erase(it);
  62.     }
  63.  
  64.     cout << *sums.rbegin() << '\n';
  65.   }
  66. }
  67.  
  68. signed main()
  69. {
  70.   pep_Guardiola;
  71.   io();
  72.   int t = 1;
  73.  // cin >> t;
  74.   while (t--)
  75.     Guardiola();
  76.   return 0;
  77. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TIeIkg
language:
C++14 (gcc 8.3)
created:
7 hours 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!