oj.uz

Submission #408948

# Submission time Handle Problem Language Result Execution time Memory
408948 2021-05-19T21:29:41 Z AmineWeslati Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 9000 ms 4904 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 aa; 
 
void ckmax(int &x, int y){x=max(x,y);}
 
const int MX=5e5+10;
vi t(MX,0);

void upd(int i){
	for(;i<=N; i+=i&-i) t[i]++;
}
int get(int i){
	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);
	aa.assign(all(A));

	vi temp;
	temp.assign(all(aa));
	FOR(i,0,Q) temp.pb(V[i]);
	sort(all(temp));

	unordered_map<int,int>mp;
	int cnt=0;
	for(int x: temp) if(!mp.count(x)) mp[x]=++cnt;

	vi a(N);
	FOR(i,0,N) a[i]=mp[aa[i]];
	FOR(i,0,Q) V[i]=mp[V[i]];

	vi ans(Q,0);
	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+1) t[i]=0;
		FOR(i,0,N){
			ckmax(vec[i],i-get(a[i]));
			upd(a[i]);
		}

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2493 ms 3816 KB Output is correct
2 Execution timed out 9020 ms 4904 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2252 KB Output isn't correct
2 Halted 0 ms 0 KB -