YEZAELP

TOI13: art (Lazy)

Mar 30th, 2021 (edited)
143
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. using pll  = pair <lli, lli>;
  6. using plL = pair <lli, pll>;
  7. using pLL = pair <pll, pll>;
  8. const lli INF = 2e18;
  9. lli tree[2*(1<<21)], lazy[2*(1<<21)];
  10. lli n, t;
  11.  
  12. void Lazy(lli idx, lli l, lli r){
  13.     tree[idx] += lazy[idx] * (r-l+1);
  14.     if(l != r){
  15.         lazy[2*idx] += lazy[idx];
  16.         lazy[2*idx+1] += lazy[idx];
  17.     }
  18.     lazy[idx] = 0;
  19. }
  20.  
  21. void update(lli idx, lli l, lli r, lli s, lli e, lli val){
  22.     if(lazy[idx] != 0) Lazy(idx, l, r);
  23.     if(l > e or r < s) return ;
  24.     if(s <= l and r <= e){
  25.         if(l != r){
  26.             lazy[2*idx] += val;
  27.             lazy[2*idx + 1] += val;
  28.         }
  29.         tree[idx] += val * (r-l+1);
  30.         return ;
  31.     }
  32.     lli mid = (lli) (l + r)/ 2;
  33.     update(2*idx, l, mid, s, e, val);
  34.     update(2*idx + 1, mid + 1, r, s, e, val);
  35.     tree[idx] = tree[2*idx] + tree[2*idx + 1];
  36. }
  37.  
  38. lli query(lli idx, lli l, lli r, lli k){
  39.     if(lazy[idx] != 0) Lazy(idx, l, r);
  40.     if(l == r){
  41.         return tree[idx];
  42.     }
  43.     lli mid = (lli) (l + r) / 2;
  44.     if(k <= mid)
  45.         return query(2*idx, l, mid, k);
  46.     return query(2*idx+1, mid + 1, r, k);
  47. }
  48.  
  49. lli Q(){
  50.     lli l, r;
  51.     lli mn = INF;
  52.     l = 1, r = 1e6;
  53.     while(l <= r){
  54.         lli mid = (l + r) / 2;
  55.         lli color = query(1, 1, 1e6, mid);
  56.         if(color < t){
  57.             r = mid - 1;
  58.         }
  59.         else if(color == t){
  60.             mn = min(mn, mid);
  61.             r = mid - 1;
  62.         }
  63.         else {
  64.             l = mid + 1;
  65.         }
  66.     }
  67.  
  68.     lli mx = -INF;
  69.     l = 1, r = 1e6;
  70.     while(l <= r){
  71.         lli mid = (l + r) / 2;
  72.         lli color = query(1, 1, 1e6, mid);
  73.         if(color < t){
  74.             r = mid - 1;
  75.         }
  76.         else if(color == t){
  77.             mx = max(mx, mid);
  78.             l = mid + 1;
  79.         }
  80.         else {
  81.             l = mid + 1;
  82.         }
  83.     }
  84.     if(mn == INF or mx == -INF) return 0;
  85.     return mx - mn + 1;
  86. }
  87.  
  88. int main(){
  89.  
  90.     scanf("%lld%lld", &n, &t);
  91.  
  92.     vector <plL> event;
  93.     for(lli i = 1; i <= n; i ++){
  94.         lli s, h, w, c;
  95.         scanf("%lld%lld%lld%lld", &s, &h, &w, &c);
  96.         event.push_back({s, {c, h}});
  97.         event.push_back({s+w, {-1*c, h}});
  98.     }
  99.  
  100.     sort(event.begin(), event.end());
  101.     lli pre_x = -1; // x
  102.     lli ans = 0; // t color area
  103.     lli color = 0;
  104.  
  105.     for(auto e: event){
  106.         lli x = e.first;
  107.         lli c = e.second.first;
  108.         lli y = e.second.second;
  109.         if(pre_x == -1){
  110.             pre_x = x;
  111.             color += c;
  112.             update(1, 1, 1e6, 1, y, c);
  113.             continue;
  114.         }
  115.         // query -> update
  116.         if(pre_x != x and color >= t) // query
  117.             ans += (lli) Q() * (x - pre_x);
  118.         // update
  119.         update(1, 1, 1e6, 1, y, c);
  120.         color += c;
  121.         pre_x = x;
  122.     }
  123.  
  124.     printf("%lld", ans);
  125.  
  126.     return 0;
  127. }
  128. /**
  129. 2 2
  130. 3 2 2 2
  131. 1 2 2 2
  132.  
  133. 4 1
  134. 2 4 4 1
  135. 1 5 5 1
  136. 2 7 7 1
  137. 1 8 8 1
  138.  
  139. 10 3
  140. 2 4 4 1
  141. 1 5 5 1
  142. 2 7 7 1
  143. 1 8 8 1
  144. 5 6 3 1
  145. 3 3 3 1
  146. 6 4 4 1
  147. 1 10 10 1
  148. 2 2 1 1
  149. 1 1 1 1
  150. **/
  151.  
RAW Paste Data Copied