답안 #70694 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70694	2018-08-23T08:50:52 Z	KLPP	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	7505 ms	2744 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;
}
/*class ST{
	lld segtree[1000000];
	lld maxsuffix[1000000];
	int n;
	public:
	void build(int a, int b,int node){
		maxsuffix[node]=0;
		if(a==b){
			segtree[node]=0;
			return;
		}
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
		segtree[node]=segtree[2*node]+segtree[2*node+1];
	}
	void init(int N){n=N;//cout<<n<<endl;
		build(0,n-1,1);
	}
	void update(int pos,lld val, int a,int b, int node){
		if(pos<a || pos>b)return;
		if(a==b){
			segtree[node]+=val;
			maxsuffix[node]=max((lld)0,segtree[node]);
			return;
		}
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
		segtree[node]=segtree[2*node]+segtree[2*node+1];
		maxsuffix[node]=max(maxsuffix[2*node+1],maxsuffix[2*node]+segtree[2*node+1]);
	}
	void update(int pos,lld val){
		update(pos,val,0,n-1,1);
	}
	void updatesuffix(int pos,lld val){
		update(n-1,val);
		if(pos>0){
			update(pos-1,val);
		}
	}
	lld query(){
		return maxsuffix[1];
	}
};
ST *arr[100];*/
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]-1]=V[i];
		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:110:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:118:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:123:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:139:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
              ~^~~~~~~~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	760 KB	Output is correct
2	Correct	60 ms	884 KB	Output is correct
3	Correct	468 ms	1184 KB	Output is correct
4	Correct	391 ms	1308 KB	Output is correct
5	Correct	410 ms	1308 KB	Output is correct
6	Correct	310 ms	1308 KB	Output is correct
7	Correct	347 ms	1308 KB	Output is correct
8	Correct	407 ms	1308 KB	Output is correct
9	Correct	393 ms	1328 KB	Output is correct
10	Correct	311 ms	1328 KB	Output is correct
11	Correct	288 ms	1328 KB	Output is correct
12	Correct	278 ms	1328 KB	Output is correct
13	Correct	293 ms	1448 KB	Output is correct
14	Correct	299 ms	1448 KB	Output is correct
15	Correct	351 ms	1448 KB	Output is correct
16	Correct	285 ms	1448 KB	Output is correct
17	Correct	274 ms	1448 KB	Output is correct
18	Correct	281 ms	1448 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	760 KB	Output is correct
2	Correct	60 ms	884 KB	Output is correct
3	Correct	468 ms	1184 KB	Output is correct
4	Correct	391 ms	1308 KB	Output is correct
5	Correct	410 ms	1308 KB	Output is correct
6	Correct	310 ms	1308 KB	Output is correct
7	Correct	347 ms	1308 KB	Output is correct
8	Correct	407 ms	1308 KB	Output is correct
9	Correct	393 ms	1328 KB	Output is correct
10	Correct	311 ms	1328 KB	Output is correct
11	Correct	288 ms	1328 KB	Output is correct
12	Correct	278 ms	1328 KB	Output is correct
13	Correct	293 ms	1448 KB	Output is correct
14	Correct	299 ms	1448 KB	Output is correct
15	Correct	351 ms	1448 KB	Output is correct
16	Correct	285 ms	1448 KB	Output is correct
17	Correct	274 ms	1448 KB	Output is correct
18	Correct	281 ms	1448 KB	Output is correct
19	Correct	5996 ms	1740 KB	Output is correct
20	Correct	7505 ms	1852 KB	Output is correct
21	Correct	6749 ms	1852 KB	Output is correct
22	Correct	7398 ms	1852 KB	Output is correct
23	Correct	4944 ms	1852 KB	Output is correct
24	Correct	4491 ms	1852 KB	Output is correct
25	Correct	4624 ms	1852 KB	Output is correct
26	Correct	4849 ms	1852 KB	Output is correct
27	Correct	5157 ms	1852 KB	Output is correct
28	Correct	4562 ms	1852 KB	Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	760 KB	Output is correct
2	Correct	60 ms	884 KB	Output is correct
3	Correct	468 ms	1184 KB	Output is correct
4	Correct	391 ms	1308 KB	Output is correct
5	Correct	410 ms	1308 KB	Output is correct
6	Correct	310 ms	1308 KB	Output is correct
7	Correct	347 ms	1308 KB	Output is correct
8	Correct	407 ms	1308 KB	Output is correct
9	Correct	393 ms	1328 KB	Output is correct
10	Correct	311 ms	1328 KB	Output is correct
11	Correct	288 ms	1328 KB	Output is correct
12	Correct	278 ms	1328 KB	Output is correct
13	Correct	293 ms	1448 KB	Output is correct
14	Correct	299 ms	1448 KB	Output is correct
15	Correct	351 ms	1448 KB	Output is correct
16	Correct	285 ms	1448 KB	Output is correct
17	Correct	274 ms	1448 KB	Output is correct
18	Correct	281 ms	1448 KB	Output is correct
19	Correct	5996 ms	1740 KB	Output is correct
20	Correct	7505 ms	1852 KB	Output is correct
21	Correct	6749 ms	1852 KB	Output is correct
22	Correct	7398 ms	1852 KB	Output is correct
23	Correct	4944 ms	1852 KB	Output is correct
24	Correct	4491 ms	1852 KB	Output is correct
25	Correct	4624 ms	1852 KB	Output is correct
26	Correct	4849 ms	1852 KB	Output is correct
27	Correct	5157 ms	1852 KB	Output is correct
28	Correct	4562 ms	1852 KB	Output is correct
29	Incorrect	32 ms	2744 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #70694

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