Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define nl "\n"
- #define ll long long
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define sz(v) (int) v.size()
- template<typename T = int>
- istream &operator>>(istream &in, vector<T> &v) {
- for (auto &x: v) in >> x;
- return in;
- }
- template<typename T = int>
- ostream &operator<<(ostream &out, const vector<T> &v) {
- for (const T &x: v) out << x << " ";
- return out;
- }
- void Sira() {
- ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #endif
- }
- struct node {
- double val;
- node() {
- val = 0;
- }
- node(double v) {
- val = v;
- }
- node(node &a, node &b) {
- val = a.val + b.val;
- }
- node(double a , double b){
- val = a + b;
- }
- };
- struct segtree{
- vector < node > tree, lazy;
- ll size = 1;
- segtree(ll n){
- while(size < n) size *= 2;
- tree.assign(size * 2, 0);
- lazy.assign(size * 2, 0);
- }
- ll query(ll l, ll r, ll idx, ll tl, ll tr){
- push(idx, tl, tr);
- if(tl > r || tr < l) return 0;
- if(l <= tl && tr <= r) return tree[idx].val;
- ll mid = tl + (tr - tl) / 2;
- double left = query(l, r, idx * 2 + 1, tl, mid);
- double right = query(l, r, idx * 2 + 2, mid + 1, tr);
- return node(left, right).val;
- }
- ll query(ll l, ll r){
- return query(l, r, 0, 0, size - 1);
- }
- void push(ll idx, ll tl, ll tr){
- if(lazy[idx].val == 0) return;
- tree[idx] = node(lazy[idx], tree[idx]);
- if(tl != tr){
- lazy[idx * 2 + 1] = node(lazy[idx * 2 + 1], lazy[idx]);
- lazy[idx * 2 + 2] = node(lazy[idx * 2 + 2], lazy[idx]);
- }
- lazy[idx] = 0;
- }
- void update(ll l, ll r, double v, ll idx, ll tl, ll tr){
- push(idx, tl, tr);
- if(tl > r || tr < l) return;
- if(l <= tl && tr <= r){
- lazy[idx].val += v;
- push(idx, tl, tr);
- return;
- }
- ll mid = tl + (tr - tl) / 2;
- update(l, r, v, idx * 2 + 1, tl, mid);
- update(l, r, v, idx * 2 + 2, mid + 1, tr);
- tree[idx] = node(tree[idx * 2 + 1], tree[idx * 2 + 2]);
- }
- void update(ll l, ll r, double val){
- update(l, r, val, 0, 0, size - 1);
- }
- };
- void solve(){
- int n , k , q;
- cin >> n >> k >> q;
- vector < double > a(k + 2) , b(k + 2);
- for(int i = 1 ; i <= k ; i++){
- cin >> a[i];
- }
- for(int i = 1 ; i <= k ; i++){
- cin >> b[i];
- }
- segtree st(n + 1);
- double last = 0 , last_t = 0;
- for(int i = 1 ; i <= k ; i++){
- double curr = a[i] - last;
- double curr2 = b[i] - last_t;
- // cout << a[i - 1] << " " << a[i] << " " << curr2 / curr << nl;
- st.update(a[i - 1] + 1 , a[i] , curr2 / curr);
- last = a[i];
- last_t = b[i];
- }
- while(q--){
- int x;
- cin >> x;
- cout << st.query(0 , x) << " ";
- }
- cout << nl;
- }
- int main() {
- Sira();
- int t = 1;
- cin >> t;
- while(t--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement