Submission #307195

#	Time	Username	Problem	Language	Result	Execution time	Memory
307195		katearima	Exercise Deadlines (CCO20_day1problem2)	C++14	17 / 25	226 ms	11896 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int s[300000],a[300000];
vector <int> v[200005];
priority_queue <int> mx;
int n,i,Ans;
int prev(int u){
	return u&(u-1);
}
int next(int u){
    return 2*u-(u&(u-1));
}
int sum(int x, int y){
	int ans=0;
	while(y>0){
		ans+=s[y];
		y=prev(y);
	}
	//x--;
	while(x>0){
	ans-=s[x];
	x=prev(x);
	}
	return ans;
}
void update(int u, long long d){
 while (u<=n){
  s[u]+=d;
  u=next(u);
 }
}

main(){
	cin>>n;
	for(i=1; i<=n; i++){
		cin>>a[i];
		v[a[i]].push_back(i);
		update(i,1);
	}

    for(i=n; i>0; i--){
        for(int j=0; j<v[i].size();j++){
            mx.push(v[i][j]);
        }
        if(mx.size()==0) {
		Ans=-1;
		break;
	   }
        else{
        int near=mx.top();
        Ans+=sum(near,n);
        //cout<<near<<' '<<n<<' '<<sum(near,n)<<endl;
        //cout<<sum(2,4)<<endl;
        update(near,-1);
        mx.pop();
    }
    }
	cout<<Ans<<endl;

}

Compilation message (stderr)

Main.cpp:35:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      |      ^
Main.cpp: In function 'int main()':
Main.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int j=0; j<v[i].size();j++){
      |                      ~^~~~~~~~~~~~

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