oj.uz

Submission #1012181

# Submission time Handle Problem Language Result Execution time Memory
1012181 2024-07-01T19:16:27 Z d4xn Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1628 KB 
#pragma GCC optimize ("Ofast")
#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 idx = b[i].second;
		int x = query(0, idx);
	
		while (R >= 0 && a[R] >= a[idx]) R--;

		if (idx <= R) x += query(idx, 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 30 ms 348 KB Output is correct
2 Correct 121 ms 344 KB Output is correct
3 Correct 1020 ms 628 KB Output is correct
4 Correct 1040 ms 620 KB Output is correct
5 Correct 1008 ms 604 KB Output is correct
6 Correct 559 ms 604 KB Output is correct
7 Correct 702 ms 600 KB Output is correct
8 Correct 823 ms 624 KB Output is correct
9 Correct 973 ms 624 KB Output is correct
10 Correct 598 ms 848 KB Output is correct
11 Correct 558 ms 624 KB Output is correct
12 Correct 583 ms 604 KB Output is correct
13 Correct 564 ms 624 KB Output is correct
14 Correct 532 ms 628 KB Output is correct
15 Correct 563 ms 616 KB Output is correct
16 Correct 583 ms 848 KB Output is correct
17 Correct 576 ms 624 KB Output is correct
18 Correct 588 ms 604 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 348 KB Output is correct
2 Correct 121 ms 344 KB Output is correct
3 Correct 1020 ms 628 KB Output is correct
4 Correct 1040 ms 620 KB Output is correct
5 Correct 1008 ms 604 KB Output is correct
6 Correct 559 ms 604 KB Output is correct
7 Correct 702 ms 600 KB Output is correct
8 Correct 823 ms 624 KB Output is correct
9 Correct 973 ms 624 KB Output is correct
10 Correct 598 ms 848 KB Output is correct
11 Correct 558 ms 624 KB Output is correct
12 Correct 583 ms 604 KB Output is correct
13 Correct 564 ms 624 KB Output is correct
14 Correct 532 ms 628 KB Output is correct
15 Correct 563 ms 616 KB Output is correct
16 Correct 583 ms 848 KB Output is correct
17 Correct 576 ms 624 KB Output is correct
18 Correct 588 ms 604 KB Output is correct
19 Execution timed out 9008 ms 600 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 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 30 ms 348 KB Output is correct
2 Correct 121 ms 344 KB Output is correct
3 Correct 1020 ms 628 KB Output is correct
4 Correct 1040 ms 620 KB Output is correct
5 Correct 1008 ms 604 KB Output is correct
6 Correct 559 ms 604 KB Output is correct
7 Correct 702 ms 600 KB Output is correct
8 Correct 823 ms 624 KB Output is correct
9 Correct 973 ms 624 KB Output is correct
10 Correct 598 ms 848 KB Output is correct
11 Correct 558 ms 624 KB Output is correct
12 Correct 583 ms 604 KB Output is correct
13 Correct 564 ms 624 KB Output is correct
14 Correct 532 ms 628 KB Output is correct
15 Correct 563 ms 616 KB Output is correct
16 Correct 583 ms 848 KB Output is correct
17 Correct 576 ms 624 KB Output is correct
18 Correct 588 ms 604 KB Output is correct
19 Execution timed out 9008 ms 600 KB Time limit exceeded
20 Halted 0 ms 0 KB -