Untitled
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