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; }