oj.uz

Submission #307195

# Submission time Handle Problem Language Result Execution time Memory
307195 2020-09-27T10:33:14 Z katearima Exercise Deadlines (CCO20_day1problem2) C++14
17 / 25
 226 ms 11896 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 9 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 7 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct
11 Correct 7 ms 5248 KB Output is correct
12 Correct 8 ms 5248 KB Output is correct
13 Correct 7 ms 5248 KB Output is correct
14 Correct 7 ms 5248 KB Output is correct
15 Correct 8 ms 5224 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 7 ms 5152 KB Output is correct
18 Correct 7 ms 5120 KB Output is correct
19 Correct 8 ms 5248 KB Output is correct
20 Correct 7 ms 5224 KB Output is correct
21 Correct 8 ms 5164 KB Output is correct
22 Correct 8 ms 5212 KB Output is correct
23 Correct 7 ms 5248 KB Output is correct
24 Correct 7 ms 5248 KB Output is correct
25 Correct 8 ms 5120 KB Output is correct
26 Correct 10 ms 5248 KB Output is correct
27 Correct 7 ms 5248 KB Output is correct
28 Correct 7 ms 5248 KB Output is correct
29 Correct 8 ms 5248 KB Output is correct
30 Correct 8 ms 5248 KB Output is correct
31 Correct 8 ms 5120 KB Output is correct
32 Correct 7 ms 5120 KB Output is correct
33 Correct 7 ms 5248 KB Output is correct
34 Correct 7 ms 5120 KB Output is correct
35 Correct 8 ms 5120 KB Output is correct
36 Correct 7 ms 5120 KB Output is correct
37 Correct 7 ms 5248 KB Output is correct
38 Correct 7 ms 5120 KB Output is correct
39 Correct 7 ms 5248 KB Output is correct
40 Correct 10 ms 5248 KB Output is correct
41 Correct 7 ms 5120 KB Output is correct
42 Correct 8 ms 5248 KB Output is correct
43 Correct 7 ms 5120 KB Output is correct
44 Correct 4 ms 4992 KB Output is correct
45 Correct 4 ms 4992 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 9 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 7 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct
11 Correct 7 ms 5248 KB Output is correct
12 Correct 8 ms 5248 KB Output is correct
13 Correct 7 ms 5248 KB Output is correct
14 Correct 7 ms 5248 KB Output is correct
15 Correct 8 ms 5224 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 7 ms 5152 KB Output is correct
18 Correct 7 ms 5120 KB Output is correct
19 Correct 8 ms 5248 KB Output is correct
20 Correct 7 ms 5224 KB Output is correct
21 Correct 8 ms 5164 KB Output is correct
22 Correct 8 ms 5212 KB Output is correct
23 Correct 7 ms 5248 KB Output is correct
24 Correct 7 ms 5248 KB Output is correct
25 Correct 8 ms 5120 KB Output is correct
26 Correct 10 ms 5248 KB Output is correct
27 Correct 7 ms 5248 KB Output is correct
28 Correct 7 ms 5248 KB Output is correct
29 Correct 8 ms 5248 KB Output is correct
30 Correct 8 ms 5248 KB Output is correct
31 Correct 8 ms 5120 KB Output is correct
32 Correct 7 ms 5120 KB Output is correct
33 Correct 7 ms 5248 KB Output is correct
34 Correct 7 ms 5120 KB Output is correct
35 Correct 8 ms 5120 KB Output is correct
36 Correct 7 ms 5120 KB Output is correct
37 Correct 7 ms 5248 KB Output is correct
38 Correct 7 ms 5120 KB Output is correct
39 Correct 7 ms 5248 KB Output is correct
40 Correct 10 ms 5248 KB Output is correct
41 Correct 7 ms 5120 KB Output is correct
42 Correct 8 ms 5248 KB Output is correct
43 Correct 7 ms 5120 KB Output is correct
44 Correct 4 ms 4992 KB Output is correct
45 Correct 4 ms 4992 KB Output is correct
46 Incorrect 226 ms 11896 KB Output isn't correct
47 Halted 0 ms 0 KB -