oj.uz

Submission #1012178

# Submission time Handle Problem Language Result Execution time Memory
1012178 2024-07-01T19:11:52 Z d4xn Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1628 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#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 344 KB Output is correct
2 Correct 123 ms 344 KB Output is correct
3 Correct 958 ms 620 KB Output is correct
4 Correct 984 ms 852 KB Output is correct
5 Correct 1079 ms 600 KB Output is correct
6 Correct 801 ms 848 KB Output is correct
7 Correct 929 ms 620 KB Output is correct
8 Correct 1024 ms 604 KB Output is correct
9 Correct 1111 ms 620 KB Output is correct
10 Correct 767 ms 624 KB Output is correct
11 Correct 744 ms 624 KB Output is correct
12 Correct 738 ms 600 KB Output is correct
13 Correct 733 ms 620 KB Output is correct
14 Correct 789 ms 620 KB Output is correct
15 Correct 811 ms 620 KB Output is correct
16 Correct 776 ms 620 KB Output is correct
17 Correct 803 ms 624 KB Output is correct
18 Correct 738 ms 604 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 344 KB Output is correct
2 Correct 123 ms 344 KB Output is correct
3 Correct 958 ms 620 KB Output is correct
4 Correct 984 ms 852 KB Output is correct
5 Correct 1079 ms 600 KB Output is correct
6 Correct 801 ms 848 KB Output is correct
7 Correct 929 ms 620 KB Output is correct
8 Correct 1024 ms 604 KB Output is correct
9 Correct 1111 ms 620 KB Output is correct
10 Correct 767 ms 624 KB Output is correct
11 Correct 744 ms 624 KB Output is correct
12 Correct 738 ms 600 KB Output is correct
13 Correct 733 ms 620 KB Output is correct
14 Correct 789 ms 620 KB Output is correct
15 Correct 811 ms 620 KB Output is correct
16 Correct 776 ms 620 KB Output is correct
17 Correct 803 ms 624 KB Output is correct
18 Correct 738 ms 604 KB Output is correct
19 Execution timed out 9066 ms 604 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 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 344 KB Output is correct
2 Correct 123 ms 344 KB Output is correct
3 Correct 958 ms 620 KB Output is correct
4 Correct 984 ms 852 KB Output is correct
5 Correct 1079 ms 600 KB Output is correct
6 Correct 801 ms 848 KB Output is correct
7 Correct 929 ms 620 KB Output is correct
8 Correct 1024 ms 604 KB Output is correct
9 Correct 1111 ms 620 KB Output is correct
10 Correct 767 ms 624 KB Output is correct
11 Correct 744 ms 624 KB Output is correct
12 Correct 738 ms 600 KB Output is correct
13 Correct 733 ms 620 KB Output is correct
14 Correct 789 ms 620 KB Output is correct
15 Correct 811 ms 620 KB Output is correct
16 Correct 776 ms 620 KB Output is correct
17 Correct 803 ms 624 KB Output is correct
18 Correct 738 ms 604 KB Output is correct
19 Execution timed out 9066 ms 604 KB Time limit exceeded
20 Halted 0 ms 0 KB -