Submission #393704

#	Time	Username	Problem	Language	Result	Execution time	Memory
393704		kshitij_sodani	Exercise Deadlines (CCO20_day1problem2)	C++14	25 / 25	231 ms	16948 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n;
llo it[200001];
int tree2[200001];
void u(int i,int j){
	while(i<=n){
		tree2[i]+=j;
		i+=(i&-i);
	}
}
int ss2(int i){
	int su=0;
	while(i>0){
		su+=tree2[i];
		i-=(i&-i);
	}
	return su;
}
int tree[4*200001];
void build(int no,int l,int r){
	if(l==r){
		tree[no]=it[l];
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
void update(int no,int l,int r,int i){
	if(l==r){
		tree[no]=-1;
	}
	else{
		int mid=(l+r)/2;
		if(i<=mid){
			update(no*2+1,l,mid,i);
		}
		else{
			update(no*2+2,mid+1,r,i);
		}
		tree[no]=max(tree[no*2+1],tree[no*2+2]);
	}
}
int query(int no,int l,int r,int i){
	if(l==r){
		return l;
	}
	int mid=(l+r)/2;
	
	if(tree[no*2+2]>=i){
		return query(no*2+2,mid+1,r,i);
	}
	else{
		return query(no*2+1,l,mid,i);
	}
	/*if(bb<l or r<aa){
		return -1;
	}
	if(aa<=l and r<=bb){
		return tree[no];
	}
	int mid=(l+r)/2;
	return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));*/
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	vector<llo> ss;
	set<llo> tt;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		it[i]--;
		tt.insert(it[i]);
		ss.pb(it[i]);
	}
	

	sort(ss.begin(),ss.end());
	for(llo i=0;i<n;i++){
		if(ss[i]<i){
			cout<<-1<<endl;
			return 0;
		}
	}
	build(0,0,n-1);
	for(int i=1;i<=n;i++){
		u(i,1);
	}
	llo ans=0;
	for(llo i=n-1;i>=0;i--){
		//llo ind=n;
		//continue;
		llo ind=query(0,0,n-1,i);
		/*for(int j=19;j>=0;j--){
			if(ind-(1<<j)>=0){
				//cout<<ind-(1<<j)<<":"<<query(0,0,n-1,ind-(1<<j),n-1)<<endl;
				if(query(0,0,n-1,ind-(1<<j),n-1)>=i){

				}
				else{
					//cout<<11<<endl;
					ind-=(1<<j);
				}
			}
		}*/
		//ind--;
		//cout<<ind<<":"<<endl;
		//break;
		ans+=ss2(n)-ss2(ind+1);
		update(0,0,n-1,ind);
		u(ind+1,-1);
		//cout<<ind<<":"<<endl;
		//break;
		/*for(llo j=0;j<=i;j++){
			if(it[j]==i){
				ind=j;
			}
		}
		for(llo j=ind;j<i;j++){
			ans+=1;
			swap(it[j],it[j+1]);
		}
		for(llo j=0;j<n;j++){
			it[j]=min(it[j],i-1);
		}*/

	}
	cout<<ans<<endl;
	return 0;
/*	for(llo i=0;i<n;i++){
			cout<<it[i]<<",";
		}
		cout<<endl;
*/
	/*llo ans=0;
	for(auto j:tt){
		llo ind=-1;
		//cout<<j<<endl;
		while(true){
			llo st=0;

			for(llo i=max((llo)0,ind);i<n;i++){
				if(it[i]==j and i>j){
					ind=i;
					st=1;
					break;
				}
			}
			if(st==0){
				break;
			}
			llo ind2=-1;
			for(llo i=ind;i>=0;i--){
				if(it[i]>j){
					ind2=i;
					break;
				}
			}
			for(llo i=ind2;i<ind;i++){
				swap(it[i],it[i+1]);
				ans+=1;
			}

			ind-=1;
		}
	}*/
	cout<<ans<<endl;
	
	/*while(true){
		
		if(ind==-1){
			break;
		}
		for(llo i=ind;i>it[ind];i--){
			swap(it[i],it[i-1]);
			ans++;
		}
		cout<<ind<<endl;
		for(llo i=0;i<n;i++){
			cout<<it[i]<<":";
		}
		cout<<endl;
		break;
	}
	cout<<ans<<endl;
*/


 
 
	return 0;
}
 

• Subtask 1: 17 / 17
• Subtask 2: 8 / 8