Submission #534862

---

Source Code Expand

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 262144

template <class typ> struct BIT{
	vector<typ> x;
	BIT(int n):x(n,0){}
	typ sum(int a,int b){
		if(a==0){
			typ s=0;
			for(int i=b;i>=0;i=(i&(i+1))-1) s+=x[i];
			return s;
		}
		else return sum(0,b)-sum(0,a-1);
	}
	void add(int ind,typ f){
		for(int i=ind;i<x.size();i|=i+1) x[i]+=f;
	}
};

int dat[N*2+10],Add[N*2+10];
int inf=1000000000;
/*int query(int a,int b,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return inf;
	if(a<=l && r<=b) return dat[k]+Add[k];
	int vl=query(a,b,k*2+1,l,(l+r)/2);
	int vr=query(a,b,k*2+2,(l+r)/2,r);
	return Add[k]+min(vl,vr);
}*/
//[a,b)に加算する
void add(int a,int b,int x,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return;
	if(a<=l && r<=b) Add[k]+=x;
	else{
		add(a,b,x,k*2+1,l,(l+r)/2);
		add(a,b,x,k*2+2,(l+r)/2,r);
		dat[k]=min(dat[k*2+1]+Add[k*2+1],dat[k*2+2]+Add[k*2+2]);
	}
}
//最も近い0点を探す
int cal(int k=0,int l=0,int r=N,int now=0){
	if(l+1==r) return l;
	now+=Add[k];
	int vl=Add[k*2+1]+dat[k*2+1]+now;
	//cout<<(l+r)/2<<' '<<r<<' '<<vr<<endl;
	if(vl<1) return cal(k*2+1,l,(l+r)/2,now);
	else return cal(k*2+2,(l+r)/2,r,now);
}

int da2[N*2+10];
int query(int a,int b,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return inf;
	if(a<=l && r<=b) return da2[k];
	int vl=query(a,b,k*2+1,l,(l+r)/2);
	int vr=query(a,b,k*2+2,(l+r)/2,r);
	return min(vl,vr);
}
void update(int k,int a){
	k+=N-1;
	da2[k]=a;
	while(k>0){
		k=(k-1)/2;
		da2[k]=min(da2[k*2+1],da2[k*2+2]);
	}
	return;
}
int main()
{
	int n,x;
	vector<pint> a;
	vector<int> b;
	scanf("%d",&n);
	rep(i,n){
		scanf("%d",&x);a.pb(mp(x,i));
	}
	rep(i,n){
		scanf("%d",&x);b.pb(x);
	}
	sort(All(a));
	rep(i,n){
		if(b[i]>a[i].fi){
			//cout<<b[i]<<' '<<a[i].fi<<endl;
			cout<<-1<<endl;return 0;
		}
	}
	
	memset(dat,0,sizeof(dat));
	memset(Add,0,sizeof(Add));
	rep(i,N*2+10) da2[i]=inf;
	int poa[114514],pob[114514],de[114514];
	rep(i,n) de[a[i].se]=i;//rep(i,n) cout<<de[i]<<endl;
	int it=0,i2=0;
	//cout<<query(0,0)<<endl;return 0;
	while(it<n || i2<n){
		if(it>=n || (i2<n && b[i2]<=a[it].fi)){
			pob[i2]=it+i2;
			add(it+i2+1,n*2+2,1);
			i2++;
		}
		else{
			poa[it]=it+i2;
			add(it+i2+1,n*2+2,-1);
			update(it+i2,a[it].se);
			//cout<<it+i2<<' '<<a[it].se<<endl;
			it++;
		}
	}
	//cout<<query(2,4)<<endl;return 0;
	//rep(i,n) cout<<pob[i]<<endl;
	//rep(i,n) cout<<poa[i]<<endl;
	
	vector<int> ret;
	rep(i,n){
		add(pob[i],pob[i]+1,1);
		x=cal();
		int t=query(pob[i],x);
		ret.pb(t);
		//cout<<x<<' '<<t<<endl;
		update(poa[de[t]],inf);//cout<<poa[de[t]]<<endl;
		add(pob[i]+1,n*2+2,-1);
		add(poa[de[t]]+1,n*2+2,1);
		add(pob[i]+1,pob[i+1],1);
		//cout<<query(2,4)<<endl;
		//cout<<poa[a[t].se]<<endl;
	}
	
	BIT<int> bit(n+10);
	lint out=0;
	rep(i,n){
		out+=ret[i]-bit.sum(0,ret[i]);
		bit.add(ret[i],1);
	}
	cout<<out<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:102:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:104:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);a.pb(mp(x,i));
                 ^
./Main.cpp:107:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);b.pb(x);
                 ^

Judge Result