読者です 読者をやめる 読者になる 読者になる

Air Pollution (AOJ2617)

何がむずいねん(バグりました。)
累積和を取るとただの隣同士のswapに帰着できて,冷静に考えるとl[i]>0だから累積和たちをマージソートする必要がある.しておわり.なんで1000点なんだ、500点位だと思う.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
int N;
ll p[100001],l[100000],s[100001];
vector<P> vc;
set<int> ids;
set<int>::iterator it;
int bit[100001];
int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i=(i&(i-1));
	}
	return s;
}
void add(int i,int x){
	while(i<=N){
		bit[i]+=x;
		i+=(i&-i);
	}
}

int main(){
	cin>>N;
	rep(i,N) cin>>p[i+1];
	rep(i,N) cin>>l[i];
	rep(i,N) p[i+1]+=p[i],s[i+1]=s[i]+l[i];
	rep1(i,N-1) vc.pb(P(p[i],i));
	sort(all(vc));
	vc.insert(vc.begin(),P(0,0));
	vc.pb(P(p[N],0));
	rep(i,N) if(vc[i+1].fs-vc[i].fs<l[i]){
		puts("-1");
		return 0;
	}
	ll ans=0;
	for(int i=N-1;i>0;i--){
		int id=vc[i].sc;
		ans+=i-id+sum(id);
		add(id,1);
	}
	cout<<ans<<endl;
}