fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. map<ll, int> freq;
  11. set<ll> vals;
  12. multiset<ll> gaps;
  13.  
  14. void add_val(ll x) {
  15.     if (++freq[x] == 1) {
  16.         auto it = vals.insert(x).first;
  17.         auto nxt = next(it);
  18.         auto prv = (it == vals.begin() ? vals.end() : prev(it));
  19.  
  20.         if (prv != vals.end() && nxt != vals.end()) {
  21.             gaps.erase(gaps.find(*nxt - *prv));
  22.         }
  23.         if (prv != vals.end()) gaps.insert(x - *prv);
  24.         if (nxt != vals.end()) gaps.insert(*nxt - x);
  25.     }
  26. }
  27.  
  28. void rem_val(ll x) {
  29.     if (--freq[x] == 0) {
  30.         auto it = vals.find(x);
  31.         auto nxt = next(it);
  32.         auto prv = (it == vals.begin() ? vals.end() : prev(it));
  33.  
  34.         if (prv != vals.end()) gaps.erase(gaps.find(x - *prv));
  35.         if (nxt != vals.end()) gaps.erase(gaps.find(*nxt - x));
  36.         if (prv != vals.end() && nxt != vals.end()) {
  37.             gaps.insert(*nxt - *prv);
  38.         }
  39.         vals.erase(it);
  40.     }
  41. }
  42.  
  43. ll get_ans() {
  44.     if (vals.empty()) return 0;
  45.     ll max_val = *vals.rbegin();
  46.     ll max_gap = (gaps.empty() ? 0 : *gaps.rbegin());
  47.     return max_val + max_gap;
  48. }
  49.  
  50. int main() {
  51.     ios::sync_with_stdio(false); cin.tie(NULL);
  52.  
  53.     int n, q;
  54.     cin >> n >> q;
  55.     vector<ll> a(n);
  56.     for (int i = 0; i < n; i++) {
  57.         cin >> a[i];
  58.         add_val(a[i]);
  59.     }
  60.  
  61.     while (q--) {
  62.         int idx; ll val;
  63.         cin >> idx >> val;
  64.         idx--; // Chuyển về 0-indexed nếu cần
  65.         rem_val(a[idx]);
  66.         a[idx] = val;
  67.         add_val(a[idx]);
  68.         cout << get_ans() << "\n";
  69.     }
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5 4
1 2 2 4 8
1 3
3 3
5 5
2 4
stdout
copy 
12
12
6
6
https://ideone.com/FeGGsC
5 4
1 2 2 4 8
1 3
3 3
5 5
2 4
language:
C++14 (gcc 8.3)
created:
2 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!