oj.uz

Submission #70694

# Submission time Handle Problem Language Result Execution time Memory
70694 2018-08-23T08:50:52 Z KLPP Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 7505 ms 2744 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 2744 KB Output isn't correct
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 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 -