oj.uz

Submission #70482

# Submission time Handle Problem Language Result Execution time Memory
70482 2018-08-23T04:18:04 Z KLPP Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 9000 ms 4236 KB 
#include "bubblesort2.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

class FT{
	int arr[100000];
	int n;
	public:
	void init(int N){
		n=N;
		for(int i=0;i<=n;i++){
			arr[i]=0;
		}
	}
	int query(int prefix){
		prefix++;
		int ans=0;
		for(;prefix>0;prefix-=(prefix&(-prefix))){
			ans+=arr[prefix];
		}return ans;
	}
	void update(int pos){
		pos++;
		for(;pos<=n;pos+=(pos&(-pos))){
			arr[pos]++;
		}
	}
	void print(){
		for(int i=0;i<=n;i++){
			cout<<arr[i]<<" ";
		}cout<<endl;
	}
};
FT *F;
int compute(vector<int> v){
	int n=v.size();
	F->init(n);
	pair<int,int> arr[n];
	for(int i=0;i<n;i++){
		arr[i]=pair<int,int>(v[i],i);
	}sort(arr,arr+n);
	int prev=n-1;
	int ans=0;
	for(int i=n-1;i>-1;i--){
		if(i==0 || arr[i-1]!=arr[i]){
			for(int j=prev;j>=i;j--){
				ans=max(ans,F->query(arr[j].second));
			}
			for(int j=prev;j>=i;j--){
				F->update(arr[j].second);
			}
			//A->print();
			prev=i-1;
		}
	}
	return ans;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	F=new FT();
	vector<int> ans;
	for(int i=0;i<X.size();i++){
		A[X[i]]=V[i];
		ans.push_back(compute(A));
	}
	return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 760 KB Output is correct
2 Correct 61 ms 888 KB Output is correct
3 Correct 403 ms 1032 KB Output is correct
4 Correct 398 ms 1080 KB Output is correct
5 Correct 402 ms 1160 KB Output is correct
6 Correct 260 ms 1200 KB Output is correct
7 Correct 340 ms 1416 KB Output is correct
8 Correct 354 ms 1456 KB Output is correct
9 Correct 430 ms 1540 KB Output is correct
10 Correct 253 ms 1540 KB Output is correct
11 Correct 260 ms 1540 KB Output is correct
12 Correct 254 ms 1564 KB Output is correct
13 Correct 261 ms 1608 KB Output is correct
14 Correct 246 ms 1648 KB Output is correct
15 Correct 257 ms 1812 KB Output is correct
16 Correct 249 ms 1852 KB Output is correct
17 Correct 259 ms 1852 KB Output is correct
18 Correct 265 ms 1872 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 760 KB Output is correct
2 Correct 61 ms 888 KB Output is correct
3 Correct 403 ms 1032 KB Output is correct
4 Correct 398 ms 1080 KB Output is correct
5 Correct 402 ms 1160 KB Output is correct
6 Correct 260 ms 1200 KB Output is correct
7 Correct 340 ms 1416 KB Output is correct
8 Correct 354 ms 1456 KB Output is correct
9 Correct 430 ms 1540 KB Output is correct
10 Correct 253 ms 1540 KB Output is correct
11 Correct 260 ms 1540 KB Output is correct
12 Correct 254 ms 1564 KB Output is correct
13 Correct 261 ms 1608 KB Output is correct
14 Correct 246 ms 1648 KB Output is correct
15 Correct 257 ms 1812 KB Output is correct
16 Correct 249 ms 1852 KB Output is correct
17 Correct 259 ms 1852 KB Output is correct
18 Correct 265 ms 1872 KB Output is correct
19 Correct 5801 ms 2332 KB Output is correct
20 Correct 7189 ms 2728 KB Output is correct
21 Correct 6282 ms 2948 KB Output is correct
22 Correct 6837 ms 3124 KB Output is correct
23 Correct 4578 ms 3320 KB Output is correct
24 Correct 4772 ms 3460 KB Output is correct
25 Correct 4800 ms 3600 KB Output is correct
26 Correct 4793 ms 3600 KB Output is correct
27 Correct 4624 ms 3924 KB Output is correct
28 Correct 4693 ms 4140 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9019 ms 4236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 760 KB Output is correct
2 Correct 61 ms 888 KB Output is correct
3 Correct 403 ms 1032 KB Output is correct
4 Correct 398 ms 1080 KB Output is correct
5 Correct 402 ms 1160 KB Output is correct
6 Correct 260 ms 1200 KB Output is correct
7 Correct 340 ms 1416 KB Output is correct
8 Correct 354 ms 1456 KB Output is correct
9 Correct 430 ms 1540 KB Output is correct
10 Correct 253 ms 1540 KB Output is correct
11 Correct 260 ms 1540 KB Output is correct
12 Correct 254 ms 1564 KB Output is correct
13 Correct 261 ms 1608 KB Output is correct
14 Correct 246 ms 1648 KB Output is correct
15 Correct 257 ms 1812 KB Output is correct
16 Correct 249 ms 1852 KB Output is correct
17 Correct 259 ms 1852 KB Output is correct
18 Correct 265 ms 1872 KB Output is correct
19 Correct 5801 ms 2332 KB Output is correct
20 Correct 7189 ms 2728 KB Output is correct
21 Correct 6282 ms 2948 KB Output is correct
22 Correct 6837 ms 3124 KB Output is correct
23 Correct 4578 ms 3320 KB Output is correct
24 Correct 4772 ms 3460 KB Output is correct
25 Correct 4800 ms 3600 KB Output is correct
26 Correct 4793 ms 3600 KB Output is correct
27 Correct 4624 ms 3924 KB Output is correct
28 Correct 4693 ms 4140 KB Output is correct
29 Execution timed out 9019 ms 4236 KB Time limit exceeded
30 Halted 0 ms 0 KB -