oj.uz

Submission #1012177

# Submission time Handle Problem Language Result Execution time Memory
1012177 2024-07-01T19:10:52 Z vjudge1 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 = 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 44 ms 1112 KB Output is correct
2 Correct 158 ms 1116 KB Output is correct
3 Correct 1000 ms 1112 KB Output is correct
4 Correct 1058 ms 1276 KB Output is correct
5 Correct 1198 ms 1276 KB Output is correct
6 Correct 911 ms 1276 KB Output is correct
7 Correct 967 ms 1116 KB Output is correct
8 Correct 1137 ms 1272 KB Output is correct
9 Correct 1171 ms 1280 KB Output is correct
10 Correct 765 ms 1112 KB Output is correct
11 Correct 779 ms 1276 KB Output is correct
12 Correct 790 ms 1116 KB Output is correct
13 Correct 765 ms 1116 KB Output is correct
14 Correct 806 ms 1112 KB Output is correct
15 Correct 833 ms 1292 KB Output is correct
16 Correct 799 ms 1276 KB Output is correct
17 Correct 758 ms 1272 KB Output is correct
18 Correct 793 ms 1112 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1112 KB Output is correct
2 Correct 158 ms 1116 KB Output is correct
3 Correct 1000 ms 1112 KB Output is correct
4 Correct 1058 ms 1276 KB Output is correct
5 Correct 1198 ms 1276 KB Output is correct
6 Correct 911 ms 1276 KB Output is correct
7 Correct 967 ms 1116 KB Output is correct
8 Correct 1137 ms 1272 KB Output is correct
9 Correct 1171 ms 1280 KB Output is correct
10 Correct 765 ms 1112 KB Output is correct
11 Correct 779 ms 1276 KB Output is correct
12 Correct 790 ms 1116 KB Output is correct
13 Correct 765 ms 1116 KB Output is correct
14 Correct 806 ms 1112 KB Output is correct
15 Correct 833 ms 1292 KB Output is correct
16 Correct 799 ms 1276 KB Output is correct
17 Correct 758 ms 1272 KB Output is correct
18 Correct 793 ms 1112 KB Output is correct
19 Execution timed out 9023 ms 1368 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 9047 ms 1628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1112 KB Output is correct
2 Correct 158 ms 1116 KB Output is correct
3 Correct 1000 ms 1112 KB Output is correct
4 Correct 1058 ms 1276 KB Output is correct
5 Correct 1198 ms 1276 KB Output is correct
6 Correct 911 ms 1276 KB Output is correct
7 Correct 967 ms 1116 KB Output is correct
8 Correct 1137 ms 1272 KB Output is correct
9 Correct 1171 ms 1280 KB Output is correct
10 Correct 765 ms 1112 KB Output is correct
11 Correct 779 ms 1276 KB Output is correct
12 Correct 790 ms 1116 KB Output is correct
13 Correct 765 ms 1116 KB Output is correct
14 Correct 806 ms 1112 KB Output is correct
15 Correct 833 ms 1292 KB Output is correct
16 Correct 799 ms 1276 KB Output is correct
17 Correct 758 ms 1272 KB Output is correct
18 Correct 793 ms 1112 KB Output is correct
19 Execution timed out 9023 ms 1368 KB Time limit exceeded
20 Halted 0 ms 0 KB -