京都大学プログラミングコンテスト2015

Submission #535085

Source codeソースコード

#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

Task問題 G - ケンドー
User nameユーザ名 (team)kirutos
Created time投稿日時
Language言語 C++ (GCC 4.9.2)
Status状態 AC
Score得点 300
Source lengthソースコード長 2100 Byte
File nameファイル名
Exec time実行時間 136 ms
Memory usageメモリ使用量 3708 KB

Compiler messageコンパイルメッセージ

./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...

Test case

Set

Set name Score得点 / Max score Cases
Small 3 / 3 00_small_sample_00.txt,00_small_sample_01.txt,00_small_sample_02.txt,10_small_01.txt,10_small_02.txt,10_small_03.txt,10_small_04.txt,10_small_05.txt,10_small_06.txt,10_small_07.txt,10_small_08.txt,10_small_09.txt,10_small_10.txt
All 297 / 297 00_small_sample_00.txt,00_small_sample_01.txt,00_small_sample_02.txt,10_small_01.txt,10_small_02.txt,10_small_03.txt,10_small_04.txt,10_small_05.txt,10_small_06.txt,10_small_07.txt,10_small_08.txt,10_small_09.txt,10_small_10.txt,20_large_01.txt,20_large_02.txt,20_large_03.txt,20_large_04.txt,20_large_05.txt,20_large_06.txt,20_large_07.txt,20_large_08.txt,20_large_09.txt,20_large_10.txt,30_maxcase_01.txt,31_almost_maxcase_01.txt,31_almost_maxcase_02.txt,31_almost_maxcase_03.txt,31_almost_maxcase_04.txt,31_almost_maxcase_05.txt,40_bad_maxcase_01.txt,40_bad_maxcase_02.txt,40_bad_maxcase_03.txt,40_bad_maxcase_04.txt,40_bad_maxcase_05.txt,41_bad_shufflecase_01.txt,41_bad_shufflecase_02.txt,41_bad_shufflecase_03.txt,41_bad_shufflecase_04.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_small_sample_00.txt AC 35 ms 2180 KB
00_small_sample_01.txt AC 38 ms 2176 KB
00_small_sample_02.txt AC 31 ms 1788 KB
10_small_01.txt AC 32 ms 2112 KB
10_small_02.txt AC 32 ms 2100 KB
10_small_03.txt AC 32 ms 2168 KB
10_small_04.txt AC 32 ms 2176 KB
10_small_05.txt AC 32 ms 2148 KB
10_small_06.txt AC 30 ms 2172 KB
10_small_07.txt AC 32 ms 2168 KB
10_small_08.txt AC 30 ms 2168 KB
10_small_09.txt AC 30 ms 2168 KB
10_small_10.txt AC 30 ms 2208 KB
20_large_01.txt AC 129 ms 3576 KB
20_large_02.txt AC 130 ms 3572 KB
20_large_03.txt AC 135 ms 3576 KB
20_large_04.txt AC 125 ms 3636 KB
20_large_05.txt AC 136 ms 3644 KB
20_large_06.txt AC 135 ms 3576 KB
20_large_07.txt AC 132 ms 3528 KB
20_large_08.txt AC 133 ms 3608 KB
20_large_09.txt AC 128 ms 3592 KB
20_large_10.txt AC 133 ms 3516 KB
30_maxcase_01.txt AC 82 ms 3708 KB
31_almost_maxcase_01.txt AC 91 ms 3632 KB
31_almost_maxcase_02.txt AC 90 ms 3652 KB
31_almost_maxcase_03.txt AC 88 ms 3708 KB
31_almost_maxcase_04.txt AC 90 ms 3704 KB
31_almost_maxcase_05.txt AC 90 ms 3700 KB
40_bad_maxcase_01.txt AC 84 ms 3252 KB
40_bad_maxcase_02.txt AC 82 ms 3256 KB
40_bad_maxcase_03.txt AC 85 ms 3324 KB
40_bad_maxcase_04.txt AC 83 ms 3264 KB
40_bad_maxcase_05.txt AC 84 ms 3188 KB
41_bad_shufflecase_01.txt AC 101 ms 3324 KB
41_bad_shufflecase_02.txt AC 98 ms 3192 KB
41_bad_shufflecase_03.txt AC 100 ms 3192 KB
41_bad_shufflecase_04.txt AC 99 ms 3260 KB