fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define endl '\n'
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9.  
  10. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  11. const ll N = 2e5 + 5;
  12. const ll M = 1e9 + 7;
  13.  
  14. ll fen[N], fen1[N], tot;
  15. void update(ll u, ll val)
  16. {
  17.     while (u <= tot) fen[u] += val, u += u & -u;
  18. }
  19.  
  20. ll sum(ll u)
  21. {
  22.     ll res = 0;
  23.     while (u)
  24.     {
  25.         res += fen[u];
  26.         u -= u & -u;
  27.     }
  28.     return res;
  29. }
  30.  
  31. void update1(ll u, ll val)
  32. {
  33.     while (u <= tot) fen1[u] = (fen1[u] + val) % M, u += u & -u;
  34. }
  35.  
  36. ll sum1(ll u)
  37. {
  38.     ll res = 0;
  39.     while (u)
  40.     {
  41.         res += fen1[u];
  42.         res %= M;
  43.         u -= u & -u;
  44.     }
  45.     return res;
  46. }
  47.  
  48. int main()
  49. {
  50. #ifndef ONLINE_JUDGE
  51.     freopen("input.txt", "r", stdin);
  52.     freopen("output.txt", "w", stdout);
  53. #endif
  54.     fast
  55.  
  56.     vector<ll> variety;
  57.  
  58.     ll n;
  59.     cin >> n;
  60.     ll a[n], b[n];
  61.     for (auto &x : a) cin >> x;
  62.     for (auto &x : b) cin >> x;
  63.  
  64.     for (auto x : a)
  65.         variety.push_back(x);
  66.  
  67.     ll k, cnt = 0;
  68.     for (auto x : b) cnt += x;
  69.     cin >> k;
  70.     ll kuery[k][3];
  71.     for (ll i = 0; i < k; i ++)
  72.         cin >> kuery[i][0] >> kuery[i][1] >> kuery[i][2],
  73.             variety.push_back(kuery[i][1]);
  74.  
  75.     sort(variety.begin(), variety.end());
  76.     variety.erase(unique(variety.begin(), variety.end()), variety.end());
  77.     tot = variety.size();
  78.     map<ll, ll> direct;
  79.     for (ll i = 0; i < tot; i ++)direct[variety[i]] = i + 1;
  80.  
  81.     for (ll i = 0; i < n; i ++)
  82.         update(direct[a[i]], b[i]), update1(direct[a[i]], a[i] * b[i] % M);
  83.  
  84.     for (ll i = 0; i < k; i ++)
  85.     {
  86.         ll idx = kuery[i][0], x = kuery[i][1], y = kuery[i][2];
  87.         -- idx;
  88.         update(direct[a[idx]], - b[idx]);
  89.         update1(direct[a[idx]], - (a[idx] * b[idx] % M));
  90.         cnt -= b[idx];
  91.         a[idx] = x;
  92.         b[idx] = y;
  93.         cnt += b[idx];
  94.         update(direct[a[idx]], b[idx]);
  95.         update1(direct[a[idx]], a[idx] * b[idx] % M);
  96.  
  97.         ll l = 1, r = tot, res = 1;
  98.         while (l <= r)
  99.         {
  100.             ll mid = (l + r) / 2;
  101.             ll tot = sum(mid);
  102.             if (tot >= cnt - tot) res = mid, r = mid - 1;
  103.             else l = mid + 1;
  104.         }
  105.  
  106.         l = sum(res);
  107.         r = cnt - sum(res);
  108.  
  109.         ll ans = l % M * variety[res - 1] % M - sum1(res);
  110.         ans += sum1(tot) - sum1(res) - r % M * variety[res - 1] % M;
  111.         cout << (ans % M + M) % M << endl;
  112.     }
  113.  
  114. }
Runtime error #stdin #stdout 0.01s 5444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hAuOLm
language:
C++14 (gcc 8.3)
created:
2 years 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!