提出 #3989646

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}
#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

const int N = 100005;
int a[N];
ll dp[N][2], ac[N];

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	int n, q; cin >> n >> q;
	dp[0][0] = dp[0][1] = 0;
	ac[0] = 0;
	REPU(i, 0, n) {
		cin >> a[i];
		dp[i + 1][0] = dp[i][0];
		dp[i + 1][1] = dp[i][1];
		dp[i + 1][i & 1] += a[i];
		ac[i + 1] = ac[i] + a[i];
	}

	while (q--) {
		int x; cin >> x;
		int idx = lower_bound(a, a + n, x) - a;
		int rem = n - idx;
		ll ans = 0;
		int lb = 0, rb = rem + 1;
		while (rb - lb > 1) {
			int m = (lb + rb) >> 1;
			// get m cards
			int v = a[idx + m - 1];
			int u = x - v + x;
			int j = lower_bound(a, a + n, u) - a;
			if (idx + m - j <= n - (idx + m)) lb = m;
			else rb = m;
		}
		ans = ac[n] - ac[idx + lb];
		//DEBUG(idx, lb);
		if (lb > 0) {
			int v = a[idx + lb - 1];
			int u = x - v + x;
			int j = lower_bound(a, a + n, u) - a;
			--j;
			int rev = n - (idx + lb);
			amin(j, idx + lb - 1 - rev);
			//DEBUG(j);
			if (j >= 0) {
				if ((n - j + 1) & 1) j--;
				if (j >= 0) {
					ans += dp[j + 1][j & 1];
				}
			}
		}
		else {
			int v = idx - (n - idx);
			if (v > 0) {
				ans += dp[v][(v - 1) & 1];
			}
		}

		printf("%lld\n", ans);
	}

	return 0;
}

提出情報

ジャッジ結果