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

Submission #534862

Source codeソースコード

#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

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

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

./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);
^

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 334 ms 7780 KB
00_small_sample_01.txt AC 56 ms 7780 KB
00_small_sample_02.txt AC 43 ms 1632 KB
10_small_01.txt AC 58 ms 7780 KB
10_small_02.txt AC 59 ms 7780 KB
10_small_03.txt AC 60 ms 7780 KB
10_small_04.txt AC 62 ms 7776 KB
10_small_05.txt AC 62 ms 7776 KB
10_small_06.txt AC 63 ms 7776 KB
10_small_07.txt AC 63 ms 7784 KB
10_small_08.txt AC 61 ms 7776 KB
10_small_09.txt AC 60 ms 7776 KB
10_small_10.txt AC 61 ms 7784 KB
20_large_01.txt AC 476 ms 10708 KB
20_large_02.txt AC 482 ms 10712 KB
20_large_03.txt AC 511 ms 10840 KB
20_large_04.txt AC 494 ms 10836 KB
20_large_05.txt AC 485 ms 10708 KB
20_large_06.txt AC 485 ms 10832 KB
20_large_07.txt AC 456 ms 10576 KB
20_large_08.txt AC 509 ms 10836 KB
20_large_09.txt AC 512 ms 10980 KB
20_large_10.txt AC 482 ms 10712 KB
30_maxcase_01.txt AC 461 ms 10840 KB
31_almost_maxcase_01.txt AC 486 ms 10836 KB
31_almost_maxcase_02.txt AC 462 ms 10572 KB
31_almost_maxcase_03.txt AC 458 ms 10828 KB
31_almost_maxcase_04.txt AC 455 ms 10700 KB
31_almost_maxcase_05.txt AC 444 ms 10724 KB
40_bad_maxcase_01.txt AC 99 ms 3048 KB
40_bad_maxcase_02.txt AC 93 ms 3048 KB
40_bad_maxcase_03.txt AC 98 ms 3016 KB
40_bad_maxcase_04.txt AC 98 ms 3016 KB
40_bad_maxcase_05.txt AC 91 ms 3024 KB
41_bad_shufflecase_01.txt AC 103 ms 3036 KB
41_bad_shufflecase_02.txt AC 100 ms 3048 KB
41_bad_shufflecase_03.txt AC 97 ms 3020 KB
41_bad_shufflecase_04.txt AC 98 ms 3024 KB