oj.uz

Submission #1012179

# Submission time Handle Problem Language Result Execution time Memory
1012179 2024-07-01T19:13:23 Z d4xn Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1628 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 x = query(0, b[i].second);
	
		while (R >= 0 && query(R, n-1) == n-1 - R + 1) R--;

		if (b[i].second < R) x += query(b[i].second+1, R);

		mx = max(mx, x);

		update(b[i].second);
	}
	
	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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 348 KB Output is correct
2 Correct 128 ms 348 KB Output is correct
3 Correct 990 ms 628 KB Output is correct
4 Correct 1002 ms 620 KB Output is correct
5 Correct 1077 ms 604 KB Output is correct
6 Correct 773 ms 600 KB Output is correct
7 Correct 946 ms 632 KB Output is correct
8 Correct 1010 ms 604 KB Output is correct
9 Correct 1112 ms 604 KB Output is correct
10 Correct 729 ms 624 KB Output is correct
11 Correct 747 ms 604 KB Output is correct
12 Correct 721 ms 604 KB Output is correct
13 Correct 724 ms 600 KB Output is correct
14 Correct 694 ms 600 KB Output is correct
15 Correct 731 ms 624 KB Output is correct
16 Correct 712 ms 600 KB Output is correct
17 Correct 725 ms 620 KB Output is correct
18 Correct 710 ms 604 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 348 KB Output is correct
2 Correct 128 ms 348 KB Output is correct
3 Correct 990 ms 628 KB Output is correct
4 Correct 1002 ms 620 KB Output is correct
5 Correct 1077 ms 604 KB Output is correct
6 Correct 773 ms 600 KB Output is correct
7 Correct 946 ms 632 KB Output is correct
8 Correct 1010 ms 604 KB Output is correct
9 Correct 1112 ms 604 KB Output is correct
10 Correct 729 ms 624 KB Output is correct
11 Correct 747 ms 604 KB Output is correct
12 Correct 721 ms 604 KB Output is correct
13 Correct 724 ms 600 KB Output is correct
14 Correct 694 ms 600 KB Output is correct
15 Correct 731 ms 624 KB Output is correct
16 Correct 712 ms 600 KB Output is correct
17 Correct 725 ms 620 KB Output is correct
18 Correct 710 ms 604 KB Output is correct
19 Execution timed out 9027 ms 600 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 348 KB Output is correct
2 Correct 128 ms 348 KB Output is correct
3 Correct 990 ms 628 KB Output is correct
4 Correct 1002 ms 620 KB Output is correct
5 Correct 1077 ms 604 KB Output is correct
6 Correct 773 ms 600 KB Output is correct
7 Correct 946 ms 632 KB Output is correct
8 Correct 1010 ms 604 KB Output is correct
9 Correct 1112 ms 604 KB Output is correct
10 Correct 729 ms 624 KB Output is correct
11 Correct 747 ms 604 KB Output is correct
12 Correct 721 ms 604 KB Output is correct
13 Correct 724 ms 600 KB Output is correct
14 Correct 694 ms 600 KB Output is correct
15 Correct 731 ms 624 KB Output is correct
16 Correct 712 ms 600 KB Output is correct
17 Correct 725 ms 620 KB Output is correct
18 Correct 710 ms 604 KB Output is correct
19 Execution timed out 9027 ms 600 KB Time limit exceeded
20 Halted 0 ms 0 KB -