답안 #70760 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70760	2018-08-23T10:16:28 Z	KLPP	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	7223 ms	5024 KB

bubblesort2

#include "bubblesort2.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long int lld;
#define INF 1000000000
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);
			}
			prev=i-1;
		}
	}
	return ans;
}
struct node{
	int l,r;
	int val;
	node *left,*right;
};
void build(node *n,int l, int r){
	
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){F=new FT();
	if(A.size()<=8000){
	vector<int> ans;
	for(int i=0;i<X.size();i++){
		A[X[i]]=V[i];
		ans.push_back(compute(A));
	}
	return ans;
	}
	
	set<int> arr[100];
	for(int i=0;i<A.size();i++){
		arr[A[i]-1].insert(i);
		//cout<<A[i]-1<<" "<<i<<endl;
	}
	vector<int> a;
	for(int i=0;i<X.size();i++){
		arr[A[X[i]]-1].erase(X[i]);
		arr[V[i]-1].insert(X[i]);
		A[X[i]]=V[i];
		//cout<<X[i]<<" "<<V[i]<<endl;
		vector<int>H;
		for(int j=0;j<100;j++){
			if(arr[j].size()>0){
				std::set<int>::iterator it2=arr[j].begin();
				
				H.push_back(*it2);
			}
		}
		//for(int j=0;j<H.size();j++)cout<<H[j]<<endl;
		//cout<<compute(H)<<endl;
		a.push_back(compute(H));
	}//cout<<ans.size()<<endl;
	//for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
	return a;
}

Compilation message

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

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	760 KB	Output is correct
2	Correct	65 ms	888 KB	Output is correct
3	Correct	397 ms	1112 KB	Output is correct
4	Correct	418 ms	1228 KB	Output is correct
5	Correct	422 ms	1296 KB	Output is correct
6	Correct	285 ms	1296 KB	Output is correct
7	Correct	344 ms	1400 KB	Output is correct
8	Correct	389 ms	1592 KB	Output is correct
9	Correct	380 ms	1592 KB	Output is correct
10	Correct	251 ms	1592 KB	Output is correct
11	Correct	248 ms	1772 KB	Output is correct
12	Correct	256 ms	1772 KB	Output is correct
13	Correct	269 ms	1792 KB	Output is correct
14	Correct	245 ms	1792 KB	Output is correct
15	Correct	285 ms	1792 KB	Output is correct
16	Correct	249 ms	1932 KB	Output is correct
17	Correct	260 ms	1972 KB	Output is correct
18	Correct	244 ms	2016 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	760 KB	Output is correct
2	Correct	65 ms	888 KB	Output is correct
3	Correct	397 ms	1112 KB	Output is correct
4	Correct	418 ms	1228 KB	Output is correct
5	Correct	422 ms	1296 KB	Output is correct
6	Correct	285 ms	1296 KB	Output is correct
7	Correct	344 ms	1400 KB	Output is correct
8	Correct	389 ms	1592 KB	Output is correct
9	Correct	380 ms	1592 KB	Output is correct
10	Correct	251 ms	1592 KB	Output is correct
11	Correct	248 ms	1772 KB	Output is correct
12	Correct	256 ms	1772 KB	Output is correct
13	Correct	269 ms	1792 KB	Output is correct
14	Correct	245 ms	1792 KB	Output is correct
15	Correct	285 ms	1792 KB	Output is correct
16	Correct	249 ms	1932 KB	Output is correct
17	Correct	260 ms	1972 KB	Output is correct
18	Correct	244 ms	2016 KB	Output is correct
19	Correct	5494 ms	2400 KB	Output is correct
20	Correct	7223 ms	2752 KB	Output is correct
21	Correct	6350 ms	2904 KB	Output is correct
22	Correct	7118 ms	3116 KB	Output is correct
23	Correct	4756 ms	3288 KB	Output is correct
24	Correct	4650 ms	3592 KB	Output is correct
25	Correct	4583 ms	3664 KB	Output is correct
26	Correct	4733 ms	3664 KB	Output is correct
27	Correct	4793 ms	3972 KB	Output is correct
28	Correct	4525 ms	4008 KB	Output is correct

Subtask #3
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	24 ms	5024 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	760 KB	Output is correct
2	Correct	65 ms	888 KB	Output is correct
3	Correct	397 ms	1112 KB	Output is correct
4	Correct	418 ms	1228 KB	Output is correct
5	Correct	422 ms	1296 KB	Output is correct
6	Correct	285 ms	1296 KB	Output is correct
7	Correct	344 ms	1400 KB	Output is correct
8	Correct	389 ms	1592 KB	Output is correct
9	Correct	380 ms	1592 KB	Output is correct
10	Correct	251 ms	1592 KB	Output is correct
11	Correct	248 ms	1772 KB	Output is correct
12	Correct	256 ms	1772 KB	Output is correct
13	Correct	269 ms	1792 KB	Output is correct
14	Correct	245 ms	1792 KB	Output is correct
15	Correct	285 ms	1792 KB	Output is correct
16	Correct	249 ms	1932 KB	Output is correct
17	Correct	260 ms	1972 KB	Output is correct
18	Correct	244 ms	2016 KB	Output is correct
19	Correct	5494 ms	2400 KB	Output is correct
20	Correct	7223 ms	2752 KB	Output is correct
21	Correct	6350 ms	2904 KB	Output is correct
22	Correct	7118 ms	3116 KB	Output is correct
23	Correct	4756 ms	3288 KB	Output is correct
24	Correct	4650 ms	3592 KB	Output is correct
25	Correct	4583 ms	3664 KB	Output is correct
26	Correct	4733 ms	3664 KB	Output is correct
27	Correct	4793 ms	3972 KB	Output is correct
28	Correct	4525 ms	4008 KB	Output is correct
29	Incorrect	24 ms	5024 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #70760

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 0 / 22.0

Subtask #4 0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
0 / 22.0

Subtask #4
0 / 40.0