oj.uz

Submission #408773

# Submission time Handle Problem Language Result Execution time Memory
408773 2021-05-19T15:43:53 Z AmineWeslati Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 4284 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

//--------------------------------------------//

int N,Q;
vi a,aa; 

const int MX=5e5+10;

void ckmax(int &x, int y){x=max(x,y);}


vi t(MX,0);
void upd(int idx){
	int i=idx; 
	for(;i<=N; i+=i&-i){
		t[i]++;
	}
}

int get(int idx){
	int i=idx; 
	int ans=0;
	for(;i;i-=i&-i) ans+=t[i];
	return ans;
}

vi countScans(vi A,vi X,vi V){
	N=sz(A); Q=sz(X);
	a.assign(all(A));
	aa.assign(all(A));

	vi ans(Q);
	FOR(idx,0,Q){
		aa[X[idx]]=V[idx];

		vi temp;
		temp.assign(all(aa));
		sort(all(temp));

		int cnt=0;
		unordered_map<int,int>mp;
		for(int x: temp) if(!mp.count(x)) mp[x]=++cnt;
		vi a(N);
		FOR(i,0,N) a[i]=mp[aa[i]];

		vi st,vec(N);
		ROF(i,0,N){
			while(sz(st) && st.back()<a[i]) st.pop_back();

			if(!sz(st)){
				vec[i]=(i!=N-1);
			} 
			else{
				if(st.back()==i+1 && !vec[st.back()])
					vec[i]=0;
				else vec[i]=vec[st.back()]+1;
			}

			st.pb(i);
		}
		
		t.assign(N+10,0);
		FOR(i,0,N){
			ckmax(vec[i],i-get(a[i]));
			upd(a[i]);
		}

		ans[idx]=0;
		FOR(i,0,N) ckmax(ans[idx],vec[i]);

	}
	return ans; 
}

/*

4 2
1 2 3 4
0 3
2 1

*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2252 KB Output is correct
2 Correct 167 ms 2252 KB Output is correct
3 Correct 956 ms 2468 KB Output is correct
4 Correct 961 ms 2500 KB Output is correct
5 Correct 955 ms 2468 KB Output is correct
6 Correct 854 ms 2484 KB Output is correct
7 Correct 910 ms 2472 KB Output is correct
8 Correct 930 ms 2468 KB Output is correct
9 Correct 980 ms 2472 KB Output is correct
10 Correct 717 ms 2476 KB Output is correct
11 Correct 707 ms 2468 KB Output is correct
12 Correct 730 ms 2472 KB Output is correct
13 Correct 727 ms 2472 KB Output is correct
14 Correct 745 ms 2472 KB Output is correct
15 Correct 746 ms 2468 KB Output is correct
16 Correct 733 ms 2468 KB Output is correct
17 Correct 730 ms 2488 KB Output is correct
18 Correct 705 ms 2464 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2252 KB Output is correct
2 Correct 167 ms 2252 KB Output is correct
3 Correct 956 ms 2468 KB Output is correct
4 Correct 961 ms 2500 KB Output is correct
5 Correct 955 ms 2468 KB Output is correct
6 Correct 854 ms 2484 KB Output is correct
7 Correct 910 ms 2472 KB Output is correct
8 Correct 930 ms 2468 KB Output is correct
9 Correct 980 ms 2472 KB Output is correct
10 Correct 717 ms 2476 KB Output is correct
11 Correct 707 ms 2468 KB Output is correct
12 Correct 730 ms 2472 KB Output is correct
13 Correct 727 ms 2472 KB Output is correct
14 Correct 745 ms 2472 KB Output is correct
15 Correct 746 ms 2468 KB Output is correct
16 Correct 733 ms 2468 KB Output is correct
17 Correct 730 ms 2488 KB Output is correct
18 Correct 705 ms 2464 KB Output is correct
19 Execution timed out 9099 ms 3020 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6131 ms 3356 KB Output is correct
2 Execution timed out 9042 ms 4284 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2252 KB Output is correct
2 Correct 167 ms 2252 KB Output is correct
3 Correct 956 ms 2468 KB Output is correct
4 Correct 961 ms 2500 KB Output is correct
5 Correct 955 ms 2468 KB Output is correct
6 Correct 854 ms 2484 KB Output is correct
7 Correct 910 ms 2472 KB Output is correct
8 Correct 930 ms 2468 KB Output is correct
9 Correct 980 ms 2472 KB Output is correct
10 Correct 717 ms 2476 KB Output is correct
11 Correct 707 ms 2468 KB Output is correct
12 Correct 730 ms 2472 KB Output is correct
13 Correct 727 ms 2472 KB Output is correct
14 Correct 745 ms 2472 KB Output is correct
15 Correct 746 ms 2468 KB Output is correct
16 Correct 733 ms 2468 KB Output is correct
17 Correct 730 ms 2488 KB Output is correct
18 Correct 705 ms 2464 KB Output is correct
19 Execution timed out 9099 ms 3020 KB Time limit exceeded
20 Halted 0 ms 0 KB -