oj.uz

Submission #1012175

# Submission time Handle Problem Language Result Execution time Memory
1012175 2024-07-01T19:09:08 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1884 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 50000;

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 64 ms 1232 KB Output is correct
2 Correct 168 ms 1112 KB Output is correct
3 Correct 1024 ms 1116 KB Output is correct
4 Correct 1099 ms 1112 KB Output is correct
5 Correct 1263 ms 1324 KB Output is correct
6 Correct 936 ms 1112 KB Output is correct
7 Correct 1029 ms 1328 KB Output is correct
8 Correct 1128 ms 1116 KB Output is correct
9 Correct 1235 ms 1112 KB Output is correct
10 Correct 824 ms 1312 KB Output is correct
11 Correct 810 ms 1116 KB Output is correct
12 Correct 817 ms 1308 KB Output is correct
13 Correct 850 ms 1332 KB Output is correct
14 Correct 802 ms 1112 KB Output is correct
15 Correct 823 ms 1116 KB Output is correct
16 Correct 868 ms 1116 KB Output is correct
17 Correct 809 ms 1112 KB Output is correct
18 Correct 805 ms 1312 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1232 KB Output is correct
2 Correct 168 ms 1112 KB Output is correct
3 Correct 1024 ms 1116 KB Output is correct
4 Correct 1099 ms 1112 KB Output is correct
5 Correct 1263 ms 1324 KB Output is correct
6 Correct 936 ms 1112 KB Output is correct
7 Correct 1029 ms 1328 KB Output is correct
8 Correct 1128 ms 1116 KB Output is correct
9 Correct 1235 ms 1112 KB Output is correct
10 Correct 824 ms 1312 KB Output is correct
11 Correct 810 ms 1116 KB Output is correct
12 Correct 817 ms 1308 KB Output is correct
13 Correct 850 ms 1332 KB Output is correct
14 Correct 802 ms 1112 KB Output is correct
15 Correct 823 ms 1116 KB Output is correct
16 Correct 868 ms 1116 KB Output is correct
17 Correct 809 ms 1112 KB Output is correct
18 Correct 805 ms 1312 KB Output is correct
19 Execution timed out 9002 ms 1624 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9065 ms 1884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1232 KB Output is correct
2 Correct 168 ms 1112 KB Output is correct
3 Correct 1024 ms 1116 KB Output is correct
4 Correct 1099 ms 1112 KB Output is correct
5 Correct 1263 ms 1324 KB Output is correct
6 Correct 936 ms 1112 KB Output is correct
7 Correct 1029 ms 1328 KB Output is correct
8 Correct 1128 ms 1116 KB Output is correct
9 Correct 1235 ms 1112 KB Output is correct
10 Correct 824 ms 1312 KB Output is correct
11 Correct 810 ms 1116 KB Output is correct
12 Correct 817 ms 1308 KB Output is correct
13 Correct 850 ms 1332 KB Output is correct
14 Correct 802 ms 1112 KB Output is correct
15 Correct 823 ms 1116 KB Output is correct
16 Correct 868 ms 1116 KB Output is correct
17 Correct 809 ms 1112 KB Output is correct
18 Correct 805 ms 1312 KB Output is correct
19 Execution timed out 9002 ms 1624 KB Time limit exceeded
20 Halted 0 ms 0 KB -