oj.uz

Submission #1012185

# Submission time Handle Problem Language Result Execution time Memory
1012185 2024-07-01T19:19:44 Z d4xn Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 18 ms 1624 KB 
#pragma GCC optimize ("Ofast")
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 8000;

int n, seg[N*4];
pair<int, int> b[N];

void update(int x, int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p] = 1;
    return;
  }
  int mid = (l+r) >> 1;

  if (x <= mid) update(x, p*2, l, mid);
  else update(x, p*2+1, mid+1, r);

  seg[p] = seg[p*2] + seg[p*2+1];
}

int query(int L, int R, int p=1, int l=0, int r=n-1) {
  if (L <= l && r <= R) {
    return seg[p];
  }
  int mid = (l+r) >> 1;

	int x = 0;
  if (L <= mid) x += query(L, R, p*2, l, mid);
  if (mid+1 <= R) x += query(L, R, p*2+1, mid+1, r);

	return x;
}


int solve(vector<int> a) {
	memset(seg, 0, sizeof(seg));

	for (int i = 0; i < n; i++) {
		b[i] = make_pair(a[i], i);
	}
	sort(b, b+n);

	int mx = 0;
	int R = n-1;
	for (int i = n-1; i >= 0; i--) {
		int idx = b[i].second;
		int x = query(0, idx);

		update(b[i].second);

		if (x) continue;

		while (R >= 0 && a[R] >= a[idx]) R--;

		if (idx < R) x += query(idx+1, R);

		//cerr << i << " " << x << endl;

		mx = max(mx, x);
	}
	
	return mx;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	n = A.size();
	int q = X.size();
	vector<int> ans(q);

	for (int j = 0; j < q; j++) {
		A[X[j]] = V[j];
		ans[j] = solve(A);
	}

	return ans;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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