Submission #1521425

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 100005;

int n;
lint a[MAXN], b[MAXN];
vector<lint> v;

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		while(x <= n){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		int ret = 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
}bit;

int main(){
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> a[i];
		a[i] += a[i-1];
	}
	for(int i=1; i<n; i++) v.push_back(a[i]);
	sort(v.begin(), v.end());
	vector<lint> w = {v[0]};
	for(int i=1; i<v.size(); i++) w.push_back(v[i] - v[i-1]);
	w.push_back(a[n] - v.back());
	for(auto &i : w){
		int k; cin >> k;
		if(k > i){
			puts("-1");
			return 0;
		}
	}
	for(int i=1; i<n; i++){
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
	}
	lint cnt = 0;
	for(int i=1; i<n; i++){
		cnt += i - 1 - bit.query(a[i]);
		bit.add(a[i], 1);
	}
	cout << cnt << endl;
}

Submission Info

Judge Result