fork download
copy 
  1. #/**
  2. * Author: Jorge Raul Tzab Lopez
  3. * Github: https://g...content-available-to-author-only...b.com/SJMA11723
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef pair<int, int> pii;
  12. typedef pair<ll, ll> pll;
  13. typedef vector<int> vi;
  14. typedef vector<ll> vll;
  15. typedef vector<pii> vpii;
  16. typedef vector<pll> vpll;
  17.  
  18. #define all(x) (x).begin(), (x).end()
  19. #define fi first
  20. #define se second
  21. #define pb push_back
  22. #define sz(x) (int)(x).size()
  23. #define MAXK 500000
  24.  
  25. const ll MOD = 1e9 + 7;
  26.  
  27. struct segment_tree{
  28.     struct node{
  29.         ll val, lazy;
  30.         node(): val(0), lazy(0){}
  31.     };
  32.     vector<node> nodes;
  33.     segment_tree(int n){
  34.         nodes.resize(4 * n + 1);
  35.     }
  36.  
  37.     void combine_lz(ll lz, int pos){
  38.         nodes[pos].lazy += lz;
  39.     }
  40.  
  41.     void apply_lz(int pos, int tam){
  42.         nodes[pos].val += nodes[pos].lazy * tam;
  43.         nodes[pos].lazy = 0;
  44.     }
  45.  
  46.     void push_lz(int pos, int left, int right){
  47.         int len = right - left + 1;
  48.         if(1 < len){
  49.             combine_lz(nodes[pos].lazy, pos * 2);
  50.             combine_lz(nodes[pos].lazy, pos * 2 + 1);
  51.         }
  52.         apply_lz(pos, len);
  53.     }
  54.  
  55.     void update(int x, int l, int r, int left, int right, int pos = 1){
  56.         push_lz(pos, left, right);
  57.         if(r < left || right < l) return;
  58.         if(l <= left && right <= r){
  59.             combine_lz(x, pos);
  60.             push_lz(pos, left, right);
  61.             return;
  62.         }
  63.         int mid = (left + right) / 2;
  64.         update(x, l, r, left, mid, pos * 2);
  65.         update(x, l, r, mid + 1, right, pos * 2 + 1);
  66.         nodes[pos].val = nodes[pos * 2].val + nodes[pos * 2 + 1].val;
  67.     }
  68.  
  69.     int query(ll &x, int left, int right, int pos = 1){
  70.         push_lz(pos, left, right);
  71.         if(left == right) return left;
  72.         int mid = (left + right) / 2;
  73.         push_lz(pos * 2, left, mid);
  74.         if(nodes[pos * 2].val >= x) return query(x, left, mid, pos * 2);
  75.         x -= nodes[pos * 2].val;
  76.         return query(x, mid + 1, right, pos * 2 + 1);
  77.     }
  78. };
  79.  
  80. int main(){
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0);
  83.     cout.tie(0);
  84.     int n, q; cin >> n >> q;
  85.     int arr[n];
  86.     for(int &x : arr) cin >> x;
  87.  
  88.     segment_tree ST(n);
  89.     int L[MAXK + 1], R[MAXK + 1], X[MAXK + 1];
  90.     while(q--){
  91.         int k; cin >> k;        
  92.         ll N = 0;
  93.         for(int i = 0; i < k; ++i){
  94.             cin >> L[i] >> R[i] >> X[i];
  95.             ST.update(X[i], L[i], R[i], 1, n);
  96.             N += 1ll * X[i] * (R[i] - L[i] + 1);
  97.         }
  98.  
  99.         ll x = (N >> 1) + 1;
  100.         if(!(N & 1)) x--;
  101.         int pos_a = ST.query(x, 1, n);
  102.         int a = arr[pos_a - 1], b = a;
  103.         if(!(N & 1)){
  104.             ll freq = 0;
  105.             int nxt = n;
  106.             for(int i = 0; i < k; ++i){
  107.                 if(L[i] <= pos_a && pos_a <= R[i]){
  108.                     freq += X[i];
  109.                     if(pos_a + 1 <= R[i]) nxt = pos_a + 1;
  110.                 } else if(pos_a < L[i]) nxt = min(nxt, L[i]);
  111.             }
  112.             freq -= x;
  113.             if(!freq) b = arr[nxt - 1];
  114.         }
  115.  
  116.         int ans = a + b;
  117.         if(ans & 1) cout << (ans >> 1) << ".5\n";
  118.         else cout << (ans >> 1) << '\n';
  119.  
  120.         for(int i = 0; i < k; ++i)
  121.             ST.update(-X[i], L[i], R[i], 1, n);
  122.     }
  123. }
Success #stdin #stdout 0.01s 7732KB
comments (?)
stdin
copy 
7 3
-15 -9 -7 0 1 12 15
1
2 7 1
1
7 7 1
4
5 6 1
3 6 5
6 7 4
7 7 2
stdout
copy 
0.5
15
6.5
https://ideone.com/6s3SVr
language:
C++14 (gcc 8.3)
created:
1 day 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!