Submission #535085

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX


struct bit{
	int bt[100005];
	int n;
	bit(int in){
		n=in+5;
		memset(bt,0,sizeof(bt));
	}
	int sum(int p){
		p++;
		if(p<=0)return 0;
		int res=0;
		while(p){
			res+=bt[p];
			p-=(p&(-p));
		}
		return res;
	}
	int inc(int p){
		p++;
		while(p<=n){
			bt[p]++;
			p+=(p&(-p));
		}
	}
	
	int rsum(int p,int q){
		//p++; q++;
		//printf("s. %d %d %d %d\n",sum(q),sum(p-1),p,q);
		return sum(q)-sum(p-1);
	}
};


int n;
lli ia[100005];
lli ib[100005];

int pl[100005];

int main(void){
	int place[100002];
	
	scanf("%d",&n);
	rep(i,n)scanf("%d",&ia[i]);
	rep(i,n)scanf("%d",&ib[i]);
	memset(pl,-1,sizeof(pl));
	
	bit  b1(n);
	
	irep(i,n){
		if(ia[i]<ib[0]){
			printf("-1\n");
			return 0;
		}
		
		int p=((int)(upper_bound(ib,ib+n,ia[i])-ib))-1;
		
		//printf("i. %d p. %d\n",i,p);
		
		int tp;
		if(pl[p]!=-1){
			int l=-1,r=p;
			while(r-l>1){
				int m=(l+r)/2;
				if(b1.rsum(m,p)==p-m+1)r=m;
				else l=m;
			}
			if(l==-1){
				printf("-1\n");
				return 0;
			}
			tp=l;
		}
		else{
			tp=p;
		}
		
		pl[tp] = i;
		b1.inc(tp);
	}
	
	lli ans=0;
	
	
	/*
	rep(i,n){
		printf("%d ",pl[i]);
	}
	printf(" .pls\n");
	*/
	
	
	bit b2(n);
	rep(i,n){
		//printf("%lld %d %d\n",ans,pl[i],b2.rsum(0,pl[i]));
		ans += i-b2.rsum(0,pl[i]);
		b2.inc(pl[i]);
	}
	

	
	/*
	rep(i,3){
		printf("%d\n",b2.rsum(0,i));
	}
	*/
	
	
	printf("%lld\n",ans);

	return 0;
}


/*
6
3 1 4 1 5 9
1 1 2 3 5 8 


4
3 1 4 1
1 1 2 3 

*/

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:67:27: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘lli* {aka long long int*}’ [-Wformat=]
  rep(i,n)scanf("%d",&ia[i]);
                           ^
./Main.cpp:68:27: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘lli* {aka long long int*}’ [-Wformat=]
  rep(i,n)scanf("%d",&ib[i]);
                           ^
./Main.cpp:66:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:67:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,n)scanf("%d",&ia[i]);
                            ^
./Main.cpp:68:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,n)scanf("%d",&ib...

Judge Result