Advertisement
esraa_syam

ee

May 10th, 2024
666
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.26 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define nl "\n"
  5. #define ll long long
  6. #define all(v) v.begin(), v.end()
  7. #define rall(v) v.rbegin(), v.rend()
  8. #define sz(v) (int) v.size()
  9.  
  10. template<typename T = int>
  11. istream &operator>>(istream &in, vector<T> &v) {
  12.     for (auto &x: v) in >> x;
  13.     return in;
  14. }
  15.  
  16. template<typename T = int>
  17. ostream &operator<<(ostream &out, const vector<T> &v) {
  18.     for (const T &x: v) out << x << " ";
  19.     return out;
  20. }
  21.  
  22. void Sira() {
  23.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  24. #ifndef ONLINE_JUDGE
  25.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  26. #endif
  27. }
  28.  
  29. struct node {
  30.     double val;
  31.  
  32.     node() {
  33.         val = 0;
  34.     }
  35.  
  36.     node(double v) {
  37.         val = v;
  38.     }
  39.  
  40.     node(node &a, node &b) {
  41.         val =  a.val + b.val;
  42.     }
  43.  
  44.     node(double a , double b){
  45.         val = a + b;
  46.     }
  47. };
  48.  
  49. struct segtree{
  50.     vector < node > tree, lazy;
  51.     ll size = 1;
  52.  
  53.     segtree(ll n){
  54.         while(size < n) size *= 2;
  55.         tree.assign(size * 2, 0);
  56.         lazy.assign(size * 2, 0);
  57.     }
  58.  
  59.     ll query(ll l, ll r, ll idx, ll tl, ll tr){
  60.         push(idx, tl, tr);
  61.         if(tl > r || tr < l) return 0;
  62.         if(l <= tl && tr <= r) return tree[idx].val;
  63.         ll mid = tl + (tr - tl) / 2;
  64.         double left = query(l, r, idx * 2 + 1, tl, mid);
  65.         double right = query(l, r, idx * 2 + 2, mid + 1, tr);
  66.         return node(left, right).val;
  67.     }
  68.  
  69.     ll query(ll l, ll r){
  70.         return query(l, r, 0, 0, size - 1);
  71.     }
  72.  
  73.     void push(ll idx, ll tl, ll tr){
  74.         if(lazy[idx].val == 0) return;
  75.         tree[idx] = node(lazy[idx], tree[idx]);
  76.         if(tl != tr){
  77.             lazy[idx * 2 + 1] = node(lazy[idx * 2 + 1], lazy[idx]);
  78.             lazy[idx * 2 + 2] = node(lazy[idx * 2 + 2], lazy[idx]);
  79.         }
  80.         lazy[idx] = 0;
  81.     }
  82.  
  83.     void update(ll l, ll r, double v, ll idx, ll tl, ll tr){
  84.         push(idx, tl, tr);
  85.         if(tl > r || tr < l) return;
  86.         if(l <= tl && tr <= r){
  87.             lazy[idx].val += v;
  88.             push(idx, tl, tr);
  89.             return;
  90.         }
  91.         ll mid = tl + (tr - tl) / 2;
  92.         update(l, r, v, idx * 2 + 1, tl, mid);
  93.         update(l, r, v, idx * 2 + 2, mid + 1, tr);
  94.         tree[idx] = node(tree[idx * 2 + 1], tree[idx * 2 + 2]);
  95.     }
  96.  
  97.     void update(ll l, ll r, double val){
  98.         update(l, r, val, 0, 0, size - 1);
  99.     }
  100. };
  101.  
  102. void solve(){
  103.     int n , k , q;
  104.     cin >> n >> k >> q;
  105.  
  106.     vector < double > a(k + 2) , b(k + 2);
  107.     for(int i = 1 ; i <= k ; i++){
  108.         cin >> a[i];
  109.     }
  110.  
  111.     for(int i = 1 ; i <= k ; i++){
  112.         cin >> b[i];
  113.     }
  114.  
  115.     segtree st(n + 1);
  116.  
  117.     double last = 0 , last_t = 0;
  118.  
  119.     for(int i = 1 ; i <= k ; i++){
  120.         double curr = a[i] - last;
  121.         double curr2 = b[i] - last_t;
  122. //        cout << a[i - 1] << " " << a[i] << " " << curr2 / curr << nl;
  123.         st.update(a[i - 1] + 1 , a[i] , curr2 / curr);
  124.         last = a[i];
  125.         last_t = b[i];
  126.     }
  127.  
  128.     while(q--){
  129.         int x;
  130.         cin >> x;
  131.         cout << st.query(0 , x) << " ";
  132.     }
  133.     cout << nl;
  134. }
  135.  
  136. int main() {
  137.     Sira();
  138.     int t = 1;
  139.     cin >> t;
  140.     while(t--){
  141.         solve();
  142.     }
  143.     return 0;
  144. }
  145.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement