oj.uz

Submission #284025

# Submission time Handle Problem Language Result Execution time Memory
284025 2020-08-26T13:38:03 Z AMnu Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 9000 ms 3452 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define i1 first
#define i2 second
using namespace std;

const int INF=1e6+5;

int N, Q;
int T[INF];
vector<int> H;
vector<pii> S;

void build(int x,int y) {
	for (int i=x;i<=y;i++) {
		T[i]=-INF;
	}
}

void update(int x,int y) {
	for (int i=x;i<N+Q;i++) {
		T[i]+=y;
	}
}

int query(int x) {
	int ret=0;
	
	for (int i=0;i<=x;i++) {
		if (T[i]>=0) {
			ret++;
		}
	}
	
	return ret;
}

int ans() {
	int ret=-INF;
	
	for (int i=0;i<N+Q;i++) {
		ret=max(ret,T[i]);
	}
	
	return ret;
}

void del(pii x) {
	int y=lower_bound(S.begin(),S.end(),x)-S.begin();
	T[y]=-INF;
	update(y+1,1);
}

void add(pii x) {
	int y=lower_bound(S.begin(),S.end(),x)-S.begin();
	T[y]=x.i2-query(y-1);
	update(y+1,-1);
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	N=A.size();
	Q=X.size();
	H=vector<int>(Q);
	S=vector<pii>(N+Q);
	
	for (int i=0;i<N;i++) {
		S[i]={A[i],i};
	}
	
	for (int i=0;i<Q;i++) {
		S[i+N]={V[i],X[i]};
	}
	
	sort(S.begin(),S.end());
	build(0,N+Q-1);
	
	for (int i=0;i<N;i++) {
		add({A[i],i});
	}
	
	for (int i=0;i<Q;i++) {
		del({A[X[i]],X[i]});
		A[X[i]]=V[i];
		add({A[X[i]],X[i]});
		H[i]=ans();
	}
	
	return H;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Incorrect 26 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Incorrect 26 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 980 KB Output is correct
2 Correct 5521 ms 1920 KB Output is correct
3 Execution timed out 9089 ms 3452 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Incorrect 26 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -