invictus_123

Untitled

Sep 21st, 2019
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair <int, int> pii;
  5. typedef vector <int> vi;
  6. typedef vector <pii> vpii;
  7. #define endl "\n"
  8. #define dbg(x) cout << "-->> " << #x << " = " << x << endl;
  9. #define fl(i, a, b) for(int i = a; i < b; i++)
  10. #define rfl(i, a, b) for(int i = a; i > b; i--)
  11. #define fll(i, a, b) for(ll i = a; i < b; i++)
  12. #define rfll(i, a, b) for(ll i = a; i > b; i--)
  13. #define pop(q) q.front(); q.pop();
  14. #define pb push_back
  15. #define mp make_pair
  16. #define ff first
  17. #define ss second
  18. #define all(v) v.begin(), v.end()
  19. #define maxv(a, b) *max_element(a, b)
  20. #define minv(a, b) *min_element(a, b)
  21. #define getv(vp, n) fl(i, 0, n) {int x; cin >> x; vp.pb(x);}
  22. #define fastaf ios::sync_with_stdio(false), cin.tie(0) , cout.tie(0)
  23. #define cases() ll t; cin >> t; while (t--)
  24. const ll mod = 1e9+7;
  25. const ll MOD = 1e18+7;
  26. int hi[500001];
  27. int tree[600000];
  28. void updateRange(int i, int st, int en, int l, int r, int val) {
  29.     if(l > r or r < st or l > en)
  30.         return;
  31.     if(st == en) {
  32.         tree[i] = val;
  33.         hi[st] = val;
  34.         return;
  35.     }
  36.     int mid = (st + en) / 2;
  37.     updateRange(2 * i, st, mid, l, r, val);
  38.     updateRange(2 * i + 1, mid + 1, en, l, r, val);
  39.     tree[i] = max(tree[2 * i], tree[2 * i + 1]);
  40.  
  41. }
  42. void update(int i, int st, int en, int idx, int val) {
  43.     if(st == en) {
  44.         tree[i] = val;
  45.         hi[idx] = val;
  46.         return;
  47.     }
  48.     int mid = (st + en) / 2;
  49.     if(idx >= st and idx <= mid)
  50.         update(2 * i, st, mid, idx, val);
  51.     else
  52.         update(2 * i + 1, mid + 1, en, idx, val);
  53.     tree[i] = max(tree[2 * i], tree[2 * i + 1]);
  54. }
  55. int query(int i, int st, int en, int l, int r) {
  56.     if(r < st or l > en)
  57.         return 0;
  58.     if(l <= st and en >= r)
  59.         return tree[i];
  60.     int mid = (st + en) / 2;
  61.     int q1 = query(2 * i, st, mid, l, r);
  62.     int q2 = query(2 * i + 1, mid + 1, en, l, r);
  63.     return max(q1, q2);
  64. }
  65. int main() {
  66.     fastaf;
  67.    
  68.     #ifndef ONLINE_JUDGE
  69.     freopen("input.txt", "r", stdin);
  70.     freopen("output.txt", "w", stdout);
  71.     #endif
  72.    
  73.     int st = 1, en = 500001;
  74.     cases() {
  75.         int l, h, p, c, x, m;
  76.         cin >> l >> h >> p >> c >> x;
  77.         m = query(1, st, en, x, x + l - 1);
  78.         if(c) {
  79.             updateRange(1, st, en, x, x + l - 1, m + 1);
  80.             update(1, st, en, x + p - 1, m + 1 + h);
  81.         }
  82.         else {
  83.             m = max(m, hi[x + p - 1] + h);
  84.             updateRange(1, st, en, x, x + l - 1, m + 1);
  85.         }
  86.     }
  87.     cout << tree[1] << endl;
  88.     return 0;
  89. }
Add Comment
Please, Sign In to add comment