Untitled

 avatar
unknown
plain_text
a year ago
10 kB
4
Indexable
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define vi vector<int>
#define pii pair<int, int>
#define ll long long
#define vii vector<pii>
#define pb push_back
#define vll vector<ll>
 
const ll INF = 1e18;
 
struct SegTree {
    int n;
    vll tmax, tadd;
    //vll vals;
    
    SegTree(){}
    
    SegTree(int nn) {
        n = nn;
       /* tmax.resize(4 * n + 1);
        tadd.resize(4 * n + 1);
        //vals.resize(n + 1);
        //for (int i = 0; i <= n; i++) vals[i] = -INF;
        for (int i = 0; i <= 4 * n; i++) tmax[i] = -INF, tadd[i] = 0;*/
        int t = 1;
        while (t < n + 1) t *= 2;
        int m = t;
        while (m < n + 1) m++;
        tmax.resize(2 * m + 2);
        tadd.resize(2 * m + 2);
        //vals.resize(n + 1);
        //for (int i = 0; i <= n; i++) vals[i] = -INF;
        for (int i = 0; i <= 2 * m + 1; i++) tmax[i] = -INF, tadd[i] = 0;
    }
    
    inline void upd(int v, ll add) {
        tmax[v] += add;
        tadd[v] += add;
    }
    
    void push(int v) {
        if (tadd[v] != 0) {
            upd(v * 2, tadd[v]);
            upd(v * 2 + 1, tadd[v]);
            tadd[v] = 0;
        }
    }
    
    void Update(int v, int tl, int tr, int l, int r, int add) {
        if (l > r) return;
        if (l == tl && r == tr) {
            tadd[v] += add;
            tmax[v] += add;
            return;
        }
        push(v);
        int tm =  (tl + tr) >> 1;
        Update(v * 2, tl, tm, l, min(r, tm), add);
        Update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, add);
        tmax[v] = max(tmax[v * 2], tmax[v * 2 + 1]);
    }
    
    void UpdatePoint(int v, int tl, int tr, int pos, ll val) {
        //cout << v << " " << tl << " " << tr << " " << pos << " " << val << endl;
        if (tl == tr) {
            tmax[v] = max(tmax[v], val);//maybe just val
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        if (pos <= tm) UpdatePoint(v * 2, tl, tm, pos, val);
        else UpdatePoint(v * 2 + 1, tm + 1, tr, pos, val);
        tmax[v] = max(tmax[v * 2], tmax[v * 2 + 1]);
    }
    
    ll Getmax(int v, int tl, int tr, int l, int r) {
        if (l > r) return -INF;
        if (l == tl && r == tr) return tmax[v];
        push(v);
        int tm = (tl + tr) >> 1;
        return max(Getmax(v * 2, tl, tm, l, min(r, tm)), Getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
    }
    
    void updatePoint(int pos, ll val) {
        //cout << pos << " " << val << " " << n << endl;
        //vals[pos] = max(vals[pos], val);
        //return;
        UpdatePoint(1, 0, n, pos, val);
    }
    
    void update(int l, int r, int add) {
        //for (int i = l; i <= r; i++) vals[i] += add;
        //return;
        Update(1, 0, n, l, r, add);
    }
    
    ll getmax(int l, int r) {
        //ll tmp = -INF;
        //for (int i = l; i <= r; i++) tmp = max(tmp, vals[i]);
        //return tmp;
        return Getmax(1, 0, n, l, r);
    }
};
 
struct sMatrix {
    int n;
    vector <vll> a;
    sMatrix(){}
    sMatrix(int nn) {
        n = nn;
        a.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            a[i].resize(n + 1);
            for (int j = 0; j <= n; j++) a[i][j] = -INF;
        }
    }
    
    ll rowMax(int row, int l, int r) {
        //cout << "rowMax = " << row << " " << l << " " << r << " ";
        ll tmp = -INF;
        for (int i = l; i <= r; i++) tmp = max(tmp, a[row][i]);
        //cout << tmp << endl;
        return tmp;
        //return rows[row].getmax(l, r);
    }
    
    ll columnMax(int column, int l, int r) {
        //cout << "colMax = " << column << " " << l << " " << r << " ";
        ll tmp = -INF;
        for (int i = l; i <= r; i++) tmp = max(tmp, a[i][column]);
        //cout << tmp << endl;
        return tmp;
        //return columns[column].getmax(l, r);
    }
    
    void addSubMatrix(int l1, int r1, int l2, int r2, int add) {
        //cout << "addSubMatrix = " << l1 << " " << r1 << " " << l2 << " " << r2 << " " << add << endl;
        for (int i = l1; i <= r1; i++) {
            for (int j = l2; j <= r2; j++) {
                a[i][j] += add;
            }
        }
    }
    
    void updatePoint(int row, int column, ll val) {
        //cout << "updatePoint" << " " << row << " " << column << " " << val << endl;
        //cout << row << " " << column << " " << val << endl;
        a[row][column] = max(a[row][column], val);
    }
    
    void print() {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) cout << a[i][j] << " ";
            cout << endl;
        }
        cout << endl;
    }
};
 
struct Matrix {
    vector<SegTree> rows, columns;
    int n;
    Matrix(){}
    Matrix(int nn) {
        n = nn;
        rows.resize(n + 1);
        columns.resize(n + 1);
        for (int i = 0; i <= n; i++) rows[i] = SegTree(n);
        for (int i = 0; i <= n; i++) columns[i] = SegTree(n); 
    }
    
    ll rowMax(int row, int l, int r) {
        return rows[row].getmax(l, r);
    }
    
    ll columnMax(int column, int l, int r) {
        return columns[column].getmax(l, r);
    }
    
    void addSubMatrix(int l1, int r1, int l2, int r2, int add) {
        for (int row = l1; row <= r1; row++) {
            rows[row].update(l2, r2, add);
        }
        for (int column = l2; column <= r2; column++) {
            columns[column].update(l1, r1, add);
        }
    }
    
    void updatePoint(int row, int column, ll val) {
        //cout << row << " " << column << " " << val << endl;
        rows[row].updatePoint(column, val);
        columns[column].updatePoint(row, val);
    }
};
 
vi x, c, e, t;
int n;
//ll dp[2][N][N];
vi Less;
vi P, Q, q, Qs, qs;
 
 
void upd(ll &a, ll b) {
    a = max(a, b);
}
 
ll Solve() {
    Matrix dp(n);
    //cout << "here" << endl;
    dp.updatePoint(0, 0, 0ll);
    for (int pos = 0; pos < n; pos++) {
        //cout << pos << endl;
        int j = Less[pos];
        //cout << pos << " " << j << " " << q[pos] << endl;
        //cout << pos << " " << j << " " << q[pos] << endl;
        if (t[pos] == 1) {
            for (int max2 = 0; max2 <= j; max2++) {//берем pos, случай с max1 < q[pos]
                //cout << dp.columnMax(max2, 0, q[pos] - 1) << endl;
                dp.updatePoint(q[pos], max2, dp.columnMax(max2, 0, q[pos] - 1) + c[pos]);
            }
            dp.addSubMatrix(q[pos] + 1, n, 0, j, c[pos]);
        }
        else {
            for (int max1 = 0; max1 <= j; max1++) {
                dp.updatePoint(max1, q[pos], dp.rowMax(max1, 0, q[pos] - 1));
            }
            dp.addSubMatrix(0, n, 0, q[pos] - 1, -c[pos]);
            dp.addSubMatrix(j + 1, n, q[pos], n, -c[pos]); 
        }
        //dp.print();
    }
    ll ans = -INF;
    for (int max1 = 1; max1 <= n; max1++) {
        ll tmp = dp.rowMax(max1, 0, n);
        //cout << max1 << " " << tmp << endl;
        ans = max(ans, tmp);
        //ans = max(ans, dp.rowMax(max1, 1, n));
    }
    //cout << ans << endl;
    return ans;
}
 
/*ll go(int pos, int max1, int max2) {
    if (dp[pos][max1][max2] != -1) return dp[pos][max1][max2];
    if (pos >= n) {
        if (!max1 && !max2) return dp[pos][max1][max2] = -INF;
        else return dp[pos][max1][max2] = 0;
    }
    dp[pos][max1][max2] = -INF;
    if (t[pos] == 1) {
        upd(dp[pos][max1][max2], go(pos + 1, max1, max2));
        int j = Less[pos]; //compressed value of the maximum number in q which is less than p[pos]
        //cout << "in = " <<  j << " " << pos << " " << max1 << " " << max2 << endl;
        if (!max2 || max2 <= j) {
            upd(dp[pos][max1][max2], go(pos + 1, max(max1, q[pos]), max2) + c[pos]);
        }
    }   
    else {
        upd(dp[pos][max1][max2], go(pos + 1, max1, max2) - c[pos]);
        int j = Less[pos];
        //cout << pos << " " << P[pos] << " " << max1 << " " << max2 << " " << j << endl;
        if (!max1 || max1 <= j) {
            upd(dp[pos][max1][max2], go(pos + 1, max1, max(max2, q[pos])));
        }
    }
    //cout << pos << " " << max1 << " " << max2 << " " << dp[pos][max1][max2] << endl;
    return dp[pos][max1][max2];
    
    /*
    ti = 1
        take
            (pos, max1, max2) -> (pos + 1, max(max1, q[pos]), max2) + c[pos] where p[pos] > max2
    
        not take
            (pos, max1, max2) -> (pos + 1, max1, max2)
            
    ti = 2
        take
            (pos, max1, max2) -> (pos + 1, max1, max2) - c[pos]
        not take
            (pos, max1, max2) -> (pos + 1, max1, max(max2, q[pos])) where p[pos] > max1
    
}*/
 
void read() {
    x.clear();
    c.clear();
    e.clear();
    t.clear();
    cin >> n;
    x.resize(n);
    c.resize(n);
    e.resize(n);
    t.resize(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    for (int i = 0; i < n; i++) cin >> e[i];
    for (int i = 0; i < n; i++) cin >> t[i];
    
}
 
void proc() {
    P.clear();
    Q.clear();
    P.resize(n);
    Q.resize(n);
    for (int i = 0; i < n; i++) P[i] = x[i] - e[i];
    for (int i = 0; i < n; i++) Q[i] = x[i] + e[i];
    vii tmp;
    for (int i = 0; i < n; i++) tmp.pb({Q[i], i});
    sort(tmp.begin(), tmp.end());
    int val = 1;
    q.clear();
    q.resize(n);
    Qs = Q;
    for (int i = 0; i < n; i++) {
        if (i) val++;
        q[tmp[i].second] = val;
        //qs[i] = val;
    }
    qs = q;
    sort(Qs.begin(), Qs.end());
    sort(qs.begin(), qs.end());
    Less.clear();
    Less.resize(n);
    for (int i = 0; i < n; i++) {
        int ptr = 0;
        while (ptr < n && Qs[ptr] < P[i]) ptr++;
        if (ptr) Less[i] = qs[ptr - 1];
        else Less[i] = 0;
        //cout << Less[i] << endl;
        //if (!ptr) Less[i] = 0;
        //else Less[i] = Less[i] = qs[ptr - 1];
        //cout << i << " " << P[i] << " " << Less[i] << endl;
    }
}
 
void print(const vi &a) {
    //cout << a.size() << endl;
    for (int x : a) cout << x << " ";
    cout << endl;
}
 
bool flag = false;
 
void solve() {
    read();
    if (flag) {
       cout << n << endl;
       print(x);
       print(c);
       print(e);
       print(t);
    }
    proc();
    //Solve();
    cout << (Solve() <= 0 ? "Yes" : "No") << "\n";
}
 
int main()
{
    int T;
    cin >> T;
    int num = 0;
    while (T--) {
        num++;
        //if (num == 36) flag = 1;
        //else flag = 0;
        solve();
    }
    return 0;
}
 
Editor is loading...
Leave a Comment