Submission #1721611

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

deque<ll> dq;
ll a[200001];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	ll sum = 0;
	for(int i = 0; i < n - 1; i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	for(int i = 0; i <= sum-a[0]-a[1]; i++)
	{
		dq.pb(i);
	}
	for(int i = 2; i < n - 1; i++)
	{
		ll v = a[i];
		for(int j = 1; j <= v*2-1; j+=2)
		{
			dq.push_front(dq[j]);
		}	
	}
	int m; cin >> m;
	for(int i = 0; i < m; i++)
	{
		int x; cin >> x;
		if(x>sum-a[0]-a[1])
		{
			cout<<x-sum+2*a[0]<<'\n';
		}
		else
		{
			cout<<dq[x]+a[0]-a[1]<<'\n';
		}
	}
}

Submission Info

Judge Result