Submission #602887

#	Time	Username	Problem	Language	Result	Execution time	Memory
602887		IvanJ	Snowball (JOI21_ho_t2)	C++17	100 / 100	1091 ms	15560 KiB

Main

#include<bits/stdc++.h>

#define pb push_back
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 5;

int n, q;
ll A[maxn], B[maxn];
vector<ll> L, R;
ll ansL[maxn], ansR[maxn];

int main() {
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++) scanf("%lld", A + i);
	for(int i = 0;i < q;i++) scanf("%lld", B + i);
	
	L.pb(min(0LL, B[0])), R.pb(max(0LL, B[0]));
	ll x = B[0];
	for(int i = 1;i < q;i++) {
		x += B[i];
		L.pb(min(L[i - 1], x));
		R.pb(max(R[i - 1], x));
	}
	for(int i = 0;i < q;i++) L[i] = -L[i];
	
	ansL[0] = L[q - 1];
	for(int i = 1;i < n;i++) {
		ll lo = 0, hi = 1e18;
		while(lo <= hi) {
			ll mid = (lo + hi) / 2;
			int pos = lower_bound(all(L), mid) - L.begin();
			if(pos != L.size() && mid + R[pos] <= A[i] - A[i - 1])
				ansL[i] = mid, lo = mid + 1;
			else hi = mid - 1;
		}
	}
	ansR[n - 1] = R[q - 1];
	for(int i = 0;i < n - 1;i++) {
		ll lo = 0, hi = 1e18;
		while(lo <= hi) {
			ll mid = (lo + hi) / 2;
			int pos = lower_bound(all(R), mid) - R.begin();
			if(pos != R.size() && mid + L[pos] <= A[i + 1] - A[i])
				ansR[i] = mid, lo = mid + 1;
			else hi = mid - 1;
		}
	}
	
	for(int i = 0;i < n;i++) printf("%lld\n", ansL[i] + ansR[i]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    if(pos != L.size() && mid + R[pos] <= A[i] - A[i - 1])
      |       ~~~~^~~~~~~~~~~
Main.cpp:48:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    if(pos != R.size() && mid + L[pos] <= A[i + 1] - A[i])
      |       ~~~~^~~~~~~~~~~
Main.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:19:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  for(int i = 0;i < n;i++) scanf("%lld", A + i);
      |                           ~~~~~^~~~~~~~~~~~~~~
Main.cpp:20:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  for(int i = 0;i < q;i++) scanf("%lld", B + i);
      |                           ~~~~~^~~~~~~~~~~~~~~

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