Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair <int, int> pii;
- typedef vector <int> vi;
- typedef vector <pii> vpii;
- #define endl "\n"
- #define dbg(x) cout << "-->> " << #x << " = " << x << endl;
- #define fl(i, a, b) for(int i = a; i < b; i++)
- #define rfl(i, a, b) for(int i = a; i > b; i--)
- #define fll(i, a, b) for(ll i = a; i < b; i++)
- #define rfll(i, a, b) for(ll i = a; i > b; i--)
- #define pop(q) q.front(); q.pop();
- #define pb push_back
- #define mp make_pair
- #define ff first
- #define ss second
- #define all(v) v.begin(), v.end()
- #define maxv(a, b) *max_element(a, b)
- #define minv(a, b) *min_element(a, b)
- #define getv(vp, n) fl(i, 0, n) {int x; cin >> x; vp.pb(x);}
- #define fastaf ios::sync_with_stdio(false), cin.tie(0) , cout.tie(0)
- #define cases() ll t; cin >> t; while (t--)
- const ll mod = 1e9+7;
- const ll MOD = 1e18+7;
- int hi[500001];
- int tree[600000];
- void updateRange(int i, int st, int en, int l, int r, int val) {
- if(l > r or r < st or l > en)
- return;
- if(st == en) {
- tree[i] = val;
- hi[st] = val;
- return;
- }
- int mid = (st + en) / 2;
- updateRange(2 * i, st, mid, l, r, val);
- updateRange(2 * i + 1, mid + 1, en, l, r, val);
- tree[i] = max(tree[2 * i], tree[2 * i + 1]);
- }
- void update(int i, int st, int en, int idx, int val) {
- if(st == en) {
- tree[i] = val;
- hi[idx] = val;
- return;
- }
- int mid = (st + en) / 2;
- if(idx >= st and idx <= mid)
- update(2 * i, st, mid, idx, val);
- else
- update(2 * i + 1, mid + 1, en, idx, val);
- tree[i] = max(tree[2 * i], tree[2 * i + 1]);
- }
- int query(int i, int st, int en, int l, int r) {
- if(r < st or l > en)
- return 0;
- if(l <= st and en >= r)
- return tree[i];
- int mid = (st + en) / 2;
- int q1 = query(2 * i, st, mid, l, r);
- int q2 = query(2 * i + 1, mid + 1, en, l, r);
- return max(q1, q2);
- }
- int main() {
- fastaf;
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int st = 1, en = 500001;
- cases() {
- int l, h, p, c, x, m;
- cin >> l >> h >> p >> c >> x;
- m = query(1, st, en, x, x + l - 1);
- if(c) {
- updateRange(1, st, en, x, x + l - 1, m + 1);
- update(1, st, en, x + p - 1, m + 1 + h);
- }
- else {
- m = max(m, hi[x + p - 1] + h);
- updateRange(1, st, en, x, x + l - 1, m + 1);
- }
- }
- cout << tree[1] << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment