oj.uz

Submission #1012180

# Submission time Handle Problem Language Result Execution time Memory
1012180 2024-07-01T19:16:18 Z vjudge1 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 28 ms 344 KB Output is correct
2 Correct 123 ms 348 KB Output is correct
3 Correct 935 ms 624 KB Output is correct
4 Correct 984 ms 620 KB Output is correct
5 Correct 929 ms 628 KB Output is correct
6 Correct 547 ms 600 KB Output is correct
7 Correct 697 ms 604 KB Output is correct
8 Correct 790 ms 856 KB Output is correct
9 Correct 972 ms 624 KB Output is correct
10 Correct 606 ms 620 KB Output is correct
11 Correct 646 ms 624 KB Output is correct
12 Correct 613 ms 628 KB Output is correct
13 Correct 646 ms 604 KB Output is correct
14 Correct 625 ms 604 KB Output is correct
15 Correct 610 ms 600 KB Output is correct
16 Correct 607 ms 604 KB Output is correct
17 Correct 621 ms 604 KB Output is correct
18 Correct 590 ms 604 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 344 KB Output is correct
2 Correct 123 ms 348 KB Output is correct
3 Correct 935 ms 624 KB Output is correct
4 Correct 984 ms 620 KB Output is correct
5 Correct 929 ms 628 KB Output is correct
6 Correct 547 ms 600 KB Output is correct
7 Correct 697 ms 604 KB Output is correct
8 Correct 790 ms 856 KB Output is correct
9 Correct 972 ms 624 KB Output is correct
10 Correct 606 ms 620 KB Output is correct
11 Correct 646 ms 624 KB Output is correct
12 Correct 613 ms 628 KB Output is correct
13 Correct 646 ms 604 KB Output is correct
14 Correct 625 ms 604 KB Output is correct
15 Correct 610 ms 600 KB Output is correct
16 Correct 607 ms 604 KB Output is correct
17 Correct 621 ms 604 KB Output is correct
18 Correct 590 ms 604 KB Output is correct
19 Execution timed out 9071 ms 604 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 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 28 ms 344 KB Output is correct
2 Correct 123 ms 348 KB Output is correct
3 Correct 935 ms 624 KB Output is correct
4 Correct 984 ms 620 KB Output is correct
5 Correct 929 ms 628 KB Output is correct
6 Correct 547 ms 600 KB Output is correct
7 Correct 697 ms 604 KB Output is correct
8 Correct 790 ms 856 KB Output is correct
9 Correct 972 ms 624 KB Output is correct
10 Correct 606 ms 620 KB Output is correct
11 Correct 646 ms 624 KB Output is correct
12 Correct 613 ms 628 KB Output is correct
13 Correct 646 ms 604 KB Output is correct
14 Correct 625 ms 604 KB Output is correct
15 Correct 610 ms 600 KB Output is correct
16 Correct 607 ms 604 KB Output is correct
17 Correct 621 ms 604 KB Output is correct
18 Correct 590 ms 604 KB Output is correct
19 Execution timed out 9071 ms 604 KB Time limit exceeded
20 Halted 0 ms 0 KB -