oj.uz

Submission #408756

# Submission time Handle Problem Language Result Execution time Memory
408756 2021-05-19T15:22:13 Z AmineWeslati Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 9000 ms 1176 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; 

const int MX=5e5+10;
/*set<int>t[MX*4];

void build(int pos=1, int tl=0, int tr=N-1){
	if(tl==tr){
		t[pos].insert(a[tl]);
		return; 
	}

	int tm=(tl+tr)/2;
	build(pos*2,tl,tm);
	build(pos*2+1,tm+1,tr);

	for(int x: t[pos*2]) t[pos].insert(x);
	for(int x: t[pos*2+1]) t[pos].insert(x);
}

void upd(int idx, int v, int vo, int pos=1, int tl=0, int tr=N-1){
	t[pos].erase(vo); 
	t[pos].insert(v); 

	if(tl==tr)
		return; 

	int tm=(tl+tr)/2;
	if(idx<=tl) upd(idx,v,vo,pos*2,tl,tm);
	else upd(idx,v,vo,pos*2+1,tm+1,tr);
}

int get(int ty, int l, int r, int v, int pos=1, int tl=0, int tr=N-1){
	if(l>r) return 0;
	if(tl==l && tr==r){
		int cnt=0;
		if(ty){
			for(int x: t[pos]){
				if(x<v) cnt++;
				else break;
			}
		}
		else{
			for(int x: t[pos]){
				if(x>v) cnt++;
			}
		}
		return cnt; 
	}

	int tm=(tl+tr)/2;
	return get(ty,l,min(r,tm),v,pos*2,tl,tm) 
		+ get(ty,max(l,tm+1),r,v,pos*2+1,tm+1,tr);
}*/

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

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

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

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

		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);
		}
	

		FOR(i,0,N){
			int cnt=0;
			FOR(j,0,i) if(a[j]>a[i]) cnt++;
			ckmax(vec[i],cnt);
		}

		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 87 ms 204 KB Output is correct
2 Correct 305 ms 332 KB Output is correct
3 Correct 4300 ms 396 KB Output is correct
4 Correct 4229 ms 400 KB Output is correct
5 Correct 4203 ms 396 KB Output is correct
6 Correct 4226 ms 400 KB Output is correct
7 Correct 4390 ms 400 KB Output is correct
8 Correct 4283 ms 404 KB Output is correct
9 Correct 4217 ms 404 KB Output is correct
10 Correct 4203 ms 424 KB Output is correct
11 Correct 4270 ms 400 KB Output is correct
12 Correct 4284 ms 396 KB Output is correct
13 Correct 4267 ms 392 KB Output is correct
14 Correct 4218 ms 392 KB Output is correct
15 Correct 4289 ms 452 KB Output is correct
16 Correct 4279 ms 396 KB Output is correct
17 Correct 4281 ms 392 KB Output is correct
18 Correct 4299 ms 396 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 204 KB Output is correct
2 Correct 305 ms 332 KB Output is correct
3 Correct 4300 ms 396 KB Output is correct
4 Correct 4229 ms 400 KB Output is correct
5 Correct 4203 ms 396 KB Output is correct
6 Correct 4226 ms 400 KB Output is correct
7 Correct 4390 ms 400 KB Output is correct
8 Correct 4283 ms 404 KB Output is correct
9 Correct 4217 ms 404 KB Output is correct
10 Correct 4203 ms 424 KB Output is correct
11 Correct 4270 ms 400 KB Output is correct
12 Correct 4284 ms 396 KB Output is correct
13 Correct 4267 ms 392 KB Output is correct
14 Correct 4218 ms 392 KB Output is correct
15 Correct 4289 ms 452 KB Output is correct
16 Correct 4279 ms 396 KB Output is correct
17 Correct 4281 ms 392 KB Output is correct
18 Correct 4299 ms 396 KB Output is correct
19 Execution timed out 9091 ms 692 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 204 KB Output is correct
2 Correct 305 ms 332 KB Output is correct
3 Correct 4300 ms 396 KB Output is correct
4 Correct 4229 ms 400 KB Output is correct
5 Correct 4203 ms 396 KB Output is correct
6 Correct 4226 ms 400 KB Output is correct
7 Correct 4390 ms 400 KB Output is correct
8 Correct 4283 ms 404 KB Output is correct
9 Correct 4217 ms 404 KB Output is correct
10 Correct 4203 ms 424 KB Output is correct
11 Correct 4270 ms 400 KB Output is correct
12 Correct 4284 ms 396 KB Output is correct
13 Correct 4267 ms 392 KB Output is correct
14 Correct 4218 ms 392 KB Output is correct
15 Correct 4289 ms 452 KB Output is correct
16 Correct 4279 ms 396 KB Output is correct
17 Correct 4281 ms 392 KB Output is correct
18 Correct 4299 ms 396 KB Output is correct
19 Execution timed out 9091 ms 692 KB Time limit exceeded
20 Halted 0 ms 0 KB -