Submission #309608

#	Time	Username	Problem	Language	Result	Execution time	Memory
309608		andriakhvichia	Exercise Deadlines (CCO20_day1problem2)	C++14	0 / 25	5 ms	768 KiB

Main

#include<iostream>
#include<vector>
#include <queue> 
using namespace std;


int n;

//guramis kodi

long long a[100001],s[100001];

int prev(int u)
{
 	return u&(u-1);
}

int next(int u)
{
 	return (u<<1)-(u&(u-1));
}

long long getsum(int a, int b)
{
	long long ans=0;
 	while(b>0)
	{
   		ans+=s[b]; b=prev(b);
 	}
 	a--;
 	while(a>0)
	{
   		ans-=s[a]; a=prev(a);
 	}
 	return ans;
}

void update(int u, long long d)
{
 	while(u<=n)
	{
   		s[u]+=d;
   		u=next(u);
 	}	
}



//
int main()
{
	cin>>n;
	vector<int>v[n+5];
	int array[n+5];
	//shemotana da vectoris sheqmna
	for(int i=1;i<=n;i++)
	{
		cin>>array[i];
	}
	
	for(int i=1;i<=n;i++)
	{
		int k=array[i];
		//cout<<"k="<<k<<" "<<"i="<<i<<endl;
		v[k].push_back(i);
	}
	//cout<<endl;
	
	
	for(int i=1;i<=n;i++)
	{
		a[i]=1;
	}
	for (int i=1;i<=n;i++)update(i,1);
	//TEST
	//mushaobs tu ara vectorebi
	/*for(int i=1;i<=n;i++)
	{
		vector<int>k=v[i];
		cout<<i<<" - ";
		for(int j=0;j<k.size();j++)
		{
			cout<<k[j]<<" ";
		}
		cout<<endl;
	}*/
	
	priority_queue<int>q; 
	
	
	int x=n-1;
	
	vector<int>k=v[n];
	for(int i=0;i<k.size();i++)
	{
		q.push(k[i]);
	}
	
	int ans=0;
	
	int l=1;
	
	while(l<n)
	{
		int mr=q.top();
		q.pop();
		//cout<<mr<<endl;
		if(x>=1)
		{
			vector<int>k=v[x];
			for(int i=0;i<k.size();i++)
			{
				q.push(k[i]);				
			}
			x--;
		}
		
		//cout<<"getsum("<<mr+1<<","<<n<<")="<<getsum(mr+1,n)<<endl;
		ans+=getsum(mr+1,n);
		update(mr,-1);
		
		if(q.empty())
		{
			//cout<<"-1"<<endl;
			break;
		}
		l++;
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:94:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i=0;i<k.size();i++)
      |              ~^~~~~~~~~
Main.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    for(int i=0;i<k.size();i++)
      |                ~^~~~~~~~~

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