mickypinata

JOI: Snowball

Dec 4th, 2021
819
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5. typedef tuple<lli, int, int> tlii;
  6.  
  7. const int N = 2e5 + 5;
  8.  
  9. deque<tlii> snow;
  10. lli weight[N];
  11.  
  12. int main(){
  13.  
  14.     int n, nDay;
  15.     scanf("%d%d", &n, &nDay);
  16.     lli lst = -1e18;
  17.     for(int i = 1; i <= n; ++i){
  18.         lli x;
  19.         scanf("%lld", &x);
  20.         snow.emplace_back(x - lst, i - 1, i);
  21.         lst = x;
  22.     }
  23.     snow.emplace_back(1e18 - lst, n, n + 1);
  24.     sort(snow.begin(), snow.end());
  25.     lli l = 0;
  26.     lli r = 0;
  27.     lli cur = 0;
  28.     while(nDay--){
  29.         lli wind;
  30.         scanf("%lld", &wind);
  31.         cur += wind;
  32.         l = max(l, -cur);
  33.         r = max(r, cur);
  34.         while(!snow.empty() && get<0>(snow.front()) <= l + r){
  35.             lli d = get<0>(snow.front());
  36.             int li = get<1>(snow.front());
  37.             int ri = get<2>(snow.front());
  38.             snow.pop_front();
  39.             if(wind > 0){
  40.                 weight[li] += d - l;
  41.                 weight[ri] += l;
  42.             } else {
  43.                 weight[li] += r;
  44.                 weight[ri] += d - r;
  45.             }
  46.         }
  47.     }
  48.     while(!snow.empty()){
  49.         lli d = get<0>(snow.front());
  50.         int li = get<1>(snow.front());
  51.         int ri = get<2>(snow.front());
  52.         snow.pop_front();
  53.         weight[li] += r;
  54.         weight[ri] += l;
  55.     }
  56.     for(int i = 1; i <= n; ++i){
  57.         cout << weight[i] << '\n';
  58.     }
  59.  
  60.     return 0;
  61. }
  62.  
RAW Paste Data