oj.uz

Submission #58411

# Submission time Handle Problem Language Result Execution time Memory
58411 2018-07-17T18:38:04 Z khohko Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 2048 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<=2005){
		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[2005];
ll slv(vector<ll> a){
	for(int i=0; i<2005; 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<2005; 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));
	}
	ll c=0,e=1;
	while(e){
		e=0;
		for(int i=0; i<n-1; i++){
			if(a[i]>a[i+1])e=1,swap(a[i],a[i+1]);
		}
		c++;
	}
	c--;
//	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]
 }
 ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 376 KB Output is correct
2 Correct 85 ms 376 KB Output is correct
3 Correct 562 ms 536 KB Output is correct
4 Correct 536 ms 612 KB Output is correct
5 Correct 532 ms 660 KB Output is correct
6 Correct 431 ms 784 KB Output is correct
7 Correct 449 ms 784 KB Output is correct
8 Correct 478 ms 784 KB Output is correct
9 Correct 548 ms 784 KB Output is correct
10 Correct 361 ms 784 KB Output is correct
11 Correct 402 ms 784 KB Output is correct
12 Correct 380 ms 784 KB Output is correct
13 Correct 409 ms 784 KB Output is correct
14 Correct 400 ms 784 KB Output is correct
15 Correct 397 ms 784 KB Output is correct
16 Correct 404 ms 784 KB Output is correct
17 Correct 402 ms 796 KB Output is correct
18 Correct 394 ms 796 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 376 KB Output is correct
2 Correct 85 ms 376 KB Output is correct
3 Correct 562 ms 536 KB Output is correct
4 Correct 536 ms 612 KB Output is correct
5 Correct 532 ms 660 KB Output is correct
6 Correct 431 ms 784 KB Output is correct
7 Correct 449 ms 784 KB Output is correct
8 Correct 478 ms 784 KB Output is correct
9 Correct 548 ms 784 KB Output is correct
10 Correct 361 ms 784 KB Output is correct
11 Correct 402 ms 784 KB Output is correct
12 Correct 380 ms 784 KB Output is correct
13 Correct 409 ms 784 KB Output is correct
14 Correct 400 ms 784 KB Output is correct
15 Correct 397 ms 784 KB Output is correct
16 Correct 404 ms 784 KB Output is correct
17 Correct 402 ms 796 KB Output is correct
18 Correct 394 ms 796 KB Output is correct
19 Incorrect 6940 ms 1016 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 376 KB Output is correct
2 Correct 85 ms 376 KB Output is correct
3 Correct 562 ms 536 KB Output is correct
4 Correct 536 ms 612 KB Output is correct
5 Correct 532 ms 660 KB Output is correct
6 Correct 431 ms 784 KB Output is correct
7 Correct 449 ms 784 KB Output is correct
8 Correct 478 ms 784 KB Output is correct
9 Correct 548 ms 784 KB Output is correct
10 Correct 361 ms 784 KB Output is correct
11 Correct 402 ms 784 KB Output is correct
12 Correct 380 ms 784 KB Output is correct
13 Correct 409 ms 784 KB Output is correct
14 Correct 400 ms 784 KB Output is correct
15 Correct 397 ms 784 KB Output is correct
16 Correct 404 ms 784 KB Output is correct
17 Correct 402 ms 796 KB Output is correct
18 Correct 394 ms 796 KB Output is correct
19 Incorrect 6940 ms 1016 KB Output isn't correct
20 Halted 0 ms 0 KB -