제출 #1143993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143993		fryingduc	Snowball (JOI21_ho_t2)	C++20	100 / 100	67 ms	14768 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, q;
long long x[maxn], w[maxn];
long long diff[maxn], res[maxn];
long long ps[maxn][2];

void solve() {
  cin >> n >> q;
  for(int i = 1; i <= n; ++i) {
    cin >> x[i];
  }
  for(int i = 1; i <= q; ++i) {
    cin >> w[i];
  }
  x[0] = -1e18, x[n + 1] = 1e18;
  for(int i = 1; i <= n + 1; ++i) {
    diff[i] = x[i] - x[i - 1];
  }
  long long sum = 0, mn = 0, mx = 0;
  vector<pair<long long, int>> events;
  for(int i = 1; i <= q; ++i) {
    long long t = w[i];
    if(t == 0) continue;
    sum += t;
    if(sum > mx) {
      t = sum;
      events.emplace_back(t - mx, 0);    
      mx = sum;
    } else if(sum < mn) {
      t = sum;
      events.emplace_back(mn - t, 1);
      mn = sum;
    }
  }
  for(int i = 0; i < (int)events.size(); ++i) {
    if(i > 0) {
      ps[i][0] = ps[i - 1][0];
      ps[i][1] = ps[i - 1][1];
    }
    ps[i][events[i].second] += events[i].first;
    events[i].first += (i > 0 ? events[i - 1].first : 0);
  }
  for(int i = 1; i <= n + 1; ++i) {
    int pos = upper_bound(events.begin(), events.end(), make_pair(diff[i], -1)) - events.begin() - 1;
    if(pos >= 0) {
      res[i - 1] += ps[pos][0], res[i] += ps[pos][1];
      diff[i] -= events[pos].first;
    }
    ++pos;
    if(pos < (int)events.size()) {
      if(events[pos].second == 0) {
        res[i - 1] += diff[i];
      } else {
        res[i] += diff[i];
      }
    }
  }
  for(int i = 1; i <= n; ++i) {
    cout << res[i] << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}
/*
4 3
-2 3 5 8
2
-4
7

4 2
-2 3 5 8 
2 -4

*/

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67