oj.uz

Submission #58413

# Submission time Handle Problem Language Result Execution time Memory
58413 2018-07-17T18:39:53 Z khohko Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1844 KB 
#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

#define ll int
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(1e17+100))

ll fw[ARRS];
ll add(ll i,ll x){
	i++;
	while(i<=8005){
		fw[i]+=x;
		i+=i&-i;
	}
}

ll sum(ll i){
	i++;
	ll p=0;
	while(i>0){
		p+=fw[i];
		i-=i&-i;
	}
	return p;
}


ll t[8005];
ll slv(vector<ll> a){
	for(int i=0; i<8005; i++)fw[i]=0;
	ll n=a.size();
	vector<pair<ll,ll> > b;
	for(int i=0; i<n; i++)b.pb({a[i],i});
	sort(b.begin(),b.end());
	ll c=1;
//	for(int i=0; i<n; i++)cout<<a[i]<<" \n"[i==n-1];
	for(int i=0; i<n; i++){
		if(i&&b[i].fr!=b[i-1].fr)c++;
		a[b[i].sc]=c;
	}
//	for(int i=0; i<n; i++)cout<<a[i]<<" \n"[i==n-1];


	for(int i=n-1; i>=0; i--){
		t[i]=sum(a[i]-1);
		add(a[i],1);
	}
	ll pas=0;
	for(int i=0; i<8005; i++)fw[i]=0;
//	for(int i=0; i<n; i++)
//		cout<<a[i]<<" \n"[i==n-1];
	for(int i=0; i<n; i++){
		//cout<<t[i]<<" "<<sum(n-a[i]-1)<<endl;
		pas=max(pas,sum(n-a[i]-1)+(t[i]?1:0));
		add(n-a[i],1);
	}
	return pas;
}

vector<int> countScans(vector<int> a,vector<int> X,vector<int> V){
	ll n;
	n=a.size();
	ll q=X.size();
	vector<ll> PAS;
//	for(int i=0; i<q; i++){
//		ll k=X[i];
//		ll p=V[i];
//		s[a[k]].erase(k);
//		a[k]=p;
//		s[a[k]].insert(k);
//		ll pas=0;
//		for(int j=1; j<=100; j++){
//			if(st[j].size())
//				v.pb({*st[j].begin(),j});
//			if(st[j].size()>1)
//				v.pb({*(--st[j].end()),j});
//			pas+=max(0,st[j].size()-2);
//		}
//		sort(v.begin(),v.end());
//		for(auto x:v){
//			g.pb(x.sc);
//		}
//		PAS.pb(pas+slv(g));
//	}
	for(int i=0; i<q; i++){
		ll k=X[i];
		ll p=V[i];
		a[k]=p;
//		cout<<slv(a)<<endl;
		PAS.pb(slv(a));
	}
//	cout<<c<<endl;
//	cout<<"-----"<<endl;
	return PAS;
}

Compilation message

bubblesort2.cpp: In function 'int add(int, int)':
bubblesort2.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:65:5: warning: variable 'n' set but not used [-Wunused-but-set-variable]
  ll n;
     ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 376 KB Output is correct
2 Correct 95 ms 488 KB Output is correct
3 Correct 537 ms 672 KB Output is correct
4 Correct 527 ms 672 KB Output is correct
5 Correct 562 ms 672 KB Output is correct
6 Correct 437 ms 672 KB Output is correct
7 Correct 495 ms 676 KB Output is correct
8 Correct 594 ms 676 KB Output is correct
9 Correct 655 ms 732 KB Output is correct
10 Correct 526 ms 744 KB Output is correct
11 Correct 461 ms 748 KB Output is correct
12 Correct 474 ms 752 KB Output is correct
13 Correct 463 ms 752 KB Output is correct
14 Correct 501 ms 772 KB Output is correct
15 Correct 522 ms 772 KB Output is correct
16 Correct 433 ms 772 KB Output is correct
17 Correct 495 ms 772 KB Output is correct
18 Correct 453 ms 776 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 376 KB Output is correct
2 Correct 95 ms 488 KB Output is correct
3 Correct 537 ms 672 KB Output is correct
4 Correct 527 ms 672 KB Output is correct
5 Correct 562 ms 672 KB Output is correct
6 Correct 437 ms 672 KB Output is correct
7 Correct 495 ms 676 KB Output is correct
8 Correct 594 ms 676 KB Output is correct
9 Correct 655 ms 732 KB Output is correct
10 Correct 526 ms 744 KB Output is correct
11 Correct 461 ms 748 KB Output is correct
12 Correct 474 ms 752 KB Output is correct
13 Correct 463 ms 752 KB Output is correct
14 Correct 501 ms 772 KB Output is correct
15 Correct 522 ms 772 KB Output is correct
16 Correct 433 ms 772 KB Output is correct
17 Correct 495 ms 772 KB Output is correct
18 Correct 453 ms 776 KB Output is correct
19 Correct 8073 ms 1012 KB Output is correct
20 Execution timed out 9070 ms 1028 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 376 KB Output is correct
2 Correct 95 ms 488 KB Output is correct
3 Correct 537 ms 672 KB Output is correct
4 Correct 527 ms 672 KB Output is correct
5 Correct 562 ms 672 KB Output is correct
6 Correct 437 ms 672 KB Output is correct
7 Correct 495 ms 676 KB Output is correct
8 Correct 594 ms 676 KB Output is correct
9 Correct 655 ms 732 KB Output is correct
10 Correct 526 ms 744 KB Output is correct
11 Correct 461 ms 748 KB Output is correct
12 Correct 474 ms 752 KB Output is correct
13 Correct 463 ms 752 KB Output is correct
14 Correct 501 ms 772 KB Output is correct
15 Correct 522 ms 772 KB Output is correct
16 Correct 433 ms 772 KB Output is correct
17 Correct 495 ms 772 KB Output is correct
18 Correct 453 ms 776 KB Output is correct
19 Correct 8073 ms 1012 KB Output is correct
20 Execution timed out 9070 ms 1028 KB Time limit exceeded
21 Halted 0 ms 0 KB -