oj.uz

Submission #1012191

# Submission time Handle Problem Language Result Execution time Memory
1012191 2024-07-01T19:27:02 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1368 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 8000, inf = INT_MAX;

int n, suf[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 = n-1; i >= 0; i--) {
		b[i] = make_pair(a[i], i);
		suf[i] = min(a[i], (i+1 < n ? suf[i+1] : inf));
	}
	sort(b, b+n);

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

		update(b[i].second);

		if (idx+1 <= n-1 && suf[idx] < a[idx]) continue;

		int x = (idx ? query(0, idx-1) : 0);

		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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 348 KB Output is correct
2 Correct 47 ms 348 KB Output is correct
3 Correct 377 ms 600 KB Output is correct
4 Correct 387 ms 848 KB Output is correct
5 Correct 377 ms 604 KB Output is correct
6 Correct 449 ms 652 KB Output is correct
7 Correct 478 ms 848 KB Output is correct
8 Correct 464 ms 600 KB Output is correct
9 Correct 354 ms 604 KB Output is correct
10 Correct 395 ms 604 KB Output is correct
11 Correct 366 ms 632 KB Output is correct
12 Correct 355 ms 632 KB Output is correct
13 Correct 391 ms 660 KB Output is correct
14 Correct 357 ms 604 KB Output is correct
15 Correct 379 ms 600 KB Output is correct
16 Correct 374 ms 632 KB Output is correct
17 Correct 367 ms 604 KB Output is correct
18 Correct 356 ms 636 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 348 KB Output is correct
2 Correct 47 ms 348 KB Output is correct
3 Correct 377 ms 600 KB Output is correct
4 Correct 387 ms 848 KB Output is correct
5 Correct 377 ms 604 KB Output is correct
6 Correct 449 ms 652 KB Output is correct
7 Correct 478 ms 848 KB Output is correct
8 Correct 464 ms 600 KB Output is correct
9 Correct 354 ms 604 KB Output is correct
10 Correct 395 ms 604 KB Output is correct
11 Correct 366 ms 632 KB Output is correct
12 Correct 355 ms 632 KB Output is correct
13 Correct 391 ms 660 KB Output is correct
14 Correct 357 ms 604 KB Output is correct
15 Correct 379 ms 600 KB Output is correct
16 Correct 374 ms 632 KB Output is correct
17 Correct 367 ms 604 KB Output is correct
18 Correct 356 ms 636 KB Output is correct
19 Correct 6257 ms 856 KB Output is correct
20 Correct 8284 ms 900 KB Output is correct
21 Execution timed out 9018 ms 856 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1368 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 20 ms 348 KB Output is correct
2 Correct 47 ms 348 KB Output is correct
3 Correct 377 ms 600 KB Output is correct
4 Correct 387 ms 848 KB Output is correct
5 Correct 377 ms 604 KB Output is correct
6 Correct 449 ms 652 KB Output is correct
7 Correct 478 ms 848 KB Output is correct
8 Correct 464 ms 600 KB Output is correct
9 Correct 354 ms 604 KB Output is correct
10 Correct 395 ms 604 KB Output is correct
11 Correct 366 ms 632 KB Output is correct
12 Correct 355 ms 632 KB Output is correct
13 Correct 391 ms 660 KB Output is correct
14 Correct 357 ms 604 KB Output is correct
15 Correct 379 ms 600 KB Output is correct
16 Correct 374 ms 632 KB Output is correct
17 Correct 367 ms 604 KB Output is correct
18 Correct 356 ms 636 KB Output is correct
19 Correct 6257 ms 856 KB Output is correct
20 Correct 8284 ms 900 KB Output is correct
21 Execution timed out 9018 ms 856 KB Time limit exceeded
22 Halted 0 ms 0 KB -