oj.uz

Submission #309608

# Submission time Handle Problem Language Result Execution time Memory
309608 2020-10-03T23:53:55 Z andriakhvichia Exercise Deadlines (CCO20_day1problem2) C++14
0 / 25
 5 ms 768 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 4 ms 640 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 4 ms 640 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 4 ms 640 KB Output is correct
23 Correct 4 ms 640 KB Output is correct
24 Correct 4 ms 640 KB Output is correct
25 Correct 4 ms 640 KB Output is correct
26 Correct 4 ms 640 KB Output is correct
27 Correct 4 ms 768 KB Output is correct
28 Correct 4 ms 640 KB Output is correct
29 Correct 4 ms 640 KB Output is correct
30 Correct 4 ms 640 KB Output is correct
31 Incorrect 4 ms 768 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 4 ms 640 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 4 ms 640 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 4 ms 640 KB Output is correct
23 Correct 4 ms 640 KB Output is correct
24 Correct 4 ms 640 KB Output is correct
25 Correct 4 ms 640 KB Output is correct
26 Correct 4 ms 640 KB Output is correct
27 Correct 4 ms 768 KB Output is correct
28 Correct 4 ms 640 KB Output is correct
29 Correct 4 ms 640 KB Output is correct
30 Correct 4 ms 640 KB Output is correct
31 Incorrect 4 ms 768 KB Output isn't correct
32 Halted 0 ms 0 KB -