oj.uz

Submission #1012194

# Submission time Handle Problem Language Result Execution time Memory
1012194 2024-07-01T19:28:29 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 7448 ms 1372 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 14 ms 344 KB Output is correct
2 Correct 32 ms 348 KB Output is correct
3 Correct 292 ms 600 KB Output is correct
4 Correct 275 ms 632 KB Output is correct
5 Correct 282 ms 600 KB Output is correct
6 Correct 373 ms 604 KB Output is correct
7 Correct 392 ms 600 KB Output is correct
8 Correct 373 ms 600 KB Output is correct
9 Correct 273 ms 636 KB Output is correct
10 Correct 272 ms 604 KB Output is correct
11 Correct 275 ms 604 KB Output is correct
12 Correct 292 ms 632 KB Output is correct
13 Correct 294 ms 852 KB Output is correct
14 Correct 299 ms 640 KB Output is correct
15 Correct 273 ms 636 KB Output is correct
16 Correct 267 ms 640 KB Output is correct
17 Correct 263 ms 604 KB Output is correct
18 Correct 257 ms 604 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 344 KB Output is correct
2 Correct 32 ms 348 KB Output is correct
3 Correct 292 ms 600 KB Output is correct
4 Correct 275 ms 632 KB Output is correct
5 Correct 282 ms 600 KB Output is correct
6 Correct 373 ms 604 KB Output is correct
7 Correct 392 ms 600 KB Output is correct
8 Correct 373 ms 600 KB Output is correct
9 Correct 273 ms 636 KB Output is correct
10 Correct 272 ms 604 KB Output is correct
11 Correct 275 ms 604 KB Output is correct
12 Correct 292 ms 632 KB Output is correct
13 Correct 294 ms 852 KB Output is correct
14 Correct 299 ms 640 KB Output is correct
15 Correct 273 ms 636 KB Output is correct
16 Correct 267 ms 640 KB Output is correct
17 Correct 263 ms 604 KB Output is correct
18 Correct 257 ms 604 KB Output is correct
19 Correct 4798 ms 856 KB Output is correct
20 Correct 6562 ms 860 KB Output is correct
21 Correct 7448 ms 888 KB Output is correct
22 Correct 6895 ms 856 KB Output is correct
23 Correct 6739 ms 880 KB Output is correct
24 Correct 6512 ms 884 KB Output is correct
25 Correct 6343 ms 888 KB Output is correct
26 Correct 6403 ms 888 KB Output is correct
27 Correct 6361 ms 900 KB Output is correct
28 Correct 6354 ms 856 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1372 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 14 ms 344 KB Output is correct
2 Correct 32 ms 348 KB Output is correct
3 Correct 292 ms 600 KB Output is correct
4 Correct 275 ms 632 KB Output is correct
5 Correct 282 ms 600 KB Output is correct
6 Correct 373 ms 604 KB Output is correct
7 Correct 392 ms 600 KB Output is correct
8 Correct 373 ms 600 KB Output is correct
9 Correct 273 ms 636 KB Output is correct
10 Correct 272 ms 604 KB Output is correct
11 Correct 275 ms 604 KB Output is correct
12 Correct 292 ms 632 KB Output is correct
13 Correct 294 ms 852 KB Output is correct
14 Correct 299 ms 640 KB Output is correct
15 Correct 273 ms 636 KB Output is correct
16 Correct 267 ms 640 KB Output is correct
17 Correct 263 ms 604 KB Output is correct
18 Correct 257 ms 604 KB Output is correct
19 Correct 4798 ms 856 KB Output is correct
20 Correct 6562 ms 860 KB Output is correct
21 Correct 7448 ms 888 KB Output is correct
22 Correct 6895 ms 856 KB Output is correct
23 Correct 6739 ms 880 KB Output is correct
24 Correct 6512 ms 884 KB Output is correct
25 Correct 6343 ms 888 KB Output is correct
26 Correct 6403 ms 888 KB Output is correct
27 Correct 6361 ms 900 KB Output is correct
28 Correct 6354 ms 856 KB Output is correct
29 Runtime error 2 ms 1372 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -