oj.uz

Submission #520008

# Submission time Handle Problem Language Result Execution time Memory
520008 2022-01-28T05:58:03 Z akhan42 Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 9000 ms 2444 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int INF = 1000 * 1000 * 1000;


struct Seg {
	int n;
	vii p1;
	vii p2;

	Seg(int n, vii &vals) {
		this->n = n;
		p1.resize(4 * n);
		p2.resize(4 * n);

		build(vals);
	}

	bool can(ii pl, ii pr) {
		return pl.S <= pr.F;
	}

	void pull(int v) {
		int lc = 2 * v, rc = 2 * v + 1;
		if(can(p1[lc], p1[rc])) {
			p1[v] = {p1[lc].F, p1[rc].S};
		} else if(can(p1[lc], p2[rc])) {
			p1[v] = {p1[lc].F, p2[rc].S};
		} else {
			p1[v] = {-1, INF};
		}

		if(can(p2[lc], p1[rc])) {
			p2[v] = {p2[lc].F, p1[rc].S};
		} else if(can(p2[lc], p2[rc])) {
			p2[v] = {p2[lc].F, p2[rc].S};
		} else {
			p2[v] = {-1, INF};
		}
	}

	void build(vii &vals, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			p1[v] = {vals[tl].F, vals[tl].F};
			p2[v] = {vals[tl].S, vals[tl].S};
			return;
		}
		int tm = (tl + tr) / 2;

		build(vals, 2 * v, tl, tm);
		build(vals, 2 * v + 1, tm + 1, tr);

		pull(v);
	}

	void set(int p, ii val, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			p1[v] = {val.F, val.F};
			p2[v] = {val.S, val.S};
			return;
		}
		int tm = (tl + tr) / 2;

		if(p <= tm)
			set(p, val, 2 * v, tl, tm);
		else
			set(p, val, 2 * v + 1, tm + 1, tr);
		pull(v);
	}

	bool is_increasing() {
		return p1[1].F != -1;
	}
};


int solve_lin(vi &a) {
	int n = sz(a);
	vii vals;
	forn(i, n) {
		vals.eb(a[i], i);
	}

	sort(all(vals));
	int mx = 0;
	forn(i, n) {
		maxeq(mx, vals[i].S - i);
	}
	return mx;
}


void solve() {
	int n, q;
	cin >> n >> q;
	vi a(n);
	forn(i, n)
		cin >> a[i];

	forn(_, q) {
		int x, v;
		cin >> x >> v;
		a[x] = v;
		cout << solve_lin(a) << '\n';
	}
}

vi countScans(vi a, vi x, vi v) {
	int n = sz(a);
	int q = sz(x);
	vi ans(q);
	forn(i, q) {
		a[x[i]] = v[i];
		ans[i] = solve_lin(a);
	}
	return ans;
}
//
//
//int main() {
//	ios_base::sync_with_stdio(false);
//	cin.tie(nullptr);
//	cout.tie(nullptr);
//
////	freopen("optmilk.in", "r", stdin);
////	freopen("optmilk.out", "w", stdout);
//
//	int t = 1;
////	cin >> t;
//	while(t--) {
//		solve();
//	}
//}

Compilation message

bubblesort2.cpp: In function 'vi countScans(vi, vi, vi)':
bubblesort2.cpp:136:6: warning: unused variable 'n' [-Wunused-variable]
  136 |  int n = sz(a);
      |      ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 204 KB Output is correct
2 Correct 35 ms 304 KB Output is correct
3 Correct 210 ms 308 KB Output is correct
4 Correct 209 ms 412 KB Output is correct
5 Correct 203 ms 428 KB Output is correct
6 Correct 136 ms 408 KB Output is correct
7 Correct 168 ms 416 KB Output is correct
8 Correct 190 ms 404 KB Output is correct
9 Correct 198 ms 412 KB Output is correct
10 Correct 126 ms 336 KB Output is correct
11 Correct 128 ms 404 KB Output is correct
12 Correct 125 ms 308 KB Output is correct
13 Correct 124 ms 456 KB Output is correct
14 Correct 129 ms 336 KB Output is correct
15 Correct 122 ms 404 KB Output is correct
16 Correct 113 ms 336 KB Output is correct
17 Correct 135 ms 464 KB Output is correct
18 Correct 112 ms 400 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 204 KB Output is correct
2 Correct 35 ms 304 KB Output is correct
3 Correct 210 ms 308 KB Output is correct
4 Correct 209 ms 412 KB Output is correct
5 Correct 203 ms 428 KB Output is correct
6 Correct 136 ms 408 KB Output is correct
7 Correct 168 ms 416 KB Output is correct
8 Correct 190 ms 404 KB Output is correct
9 Correct 198 ms 412 KB Output is correct
10 Correct 126 ms 336 KB Output is correct
11 Correct 128 ms 404 KB Output is correct
12 Correct 125 ms 308 KB Output is correct
13 Correct 124 ms 456 KB Output is correct
14 Correct 129 ms 336 KB Output is correct
15 Correct 122 ms 404 KB Output is correct
16 Correct 113 ms 336 KB Output is correct
17 Correct 135 ms 464 KB Output is correct
18 Correct 112 ms 400 KB Output is correct
19 Correct 3019 ms 756 KB Output is correct
20 Correct 3994 ms 820 KB Output is correct
21 Correct 3385 ms 820 KB Output is correct
22 Correct 3803 ms 808 KB Output is correct
23 Correct 2331 ms 788 KB Output is correct
24 Correct 2343 ms 780 KB Output is correct
25 Correct 2308 ms 772 KB Output is correct
26 Correct 2317 ms 776 KB Output is correct
27 Correct 2277 ms 776 KB Output is correct
28 Correct 2298 ms 776 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5179 ms 1432 KB Output is correct
2 Execution timed out 9026 ms 2444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 204 KB Output is correct
2 Correct 35 ms 304 KB Output is correct
3 Correct 210 ms 308 KB Output is correct
4 Correct 209 ms 412 KB Output is correct
5 Correct 203 ms 428 KB Output is correct
6 Correct 136 ms 408 KB Output is correct
7 Correct 168 ms 416 KB Output is correct
8 Correct 190 ms 404 KB Output is correct
9 Correct 198 ms 412 KB Output is correct
10 Correct 126 ms 336 KB Output is correct
11 Correct 128 ms 404 KB Output is correct
12 Correct 125 ms 308 KB Output is correct
13 Correct 124 ms 456 KB Output is correct
14 Correct 129 ms 336 KB Output is correct
15 Correct 122 ms 404 KB Output is correct
16 Correct 113 ms 336 KB Output is correct
17 Correct 135 ms 464 KB Output is correct
18 Correct 112 ms 400 KB Output is correct
19 Correct 3019 ms 756 KB Output is correct
20 Correct 3994 ms 820 KB Output is correct
21 Correct 3385 ms 820 KB Output is correct
22 Correct 3803 ms 808 KB Output is correct
23 Correct 2331 ms 788 KB Output is correct
24 Correct 2343 ms 780 KB Output is correct
25 Correct 2308 ms 772 KB Output is correct
26 Correct 2317 ms 776 KB Output is correct
27 Correct 2277 ms 776 KB Output is correct
28 Correct 2298 ms 776 KB Output is correct
29 Correct 5179 ms 1432 KB Output is correct
30 Execution timed out 9026 ms 2444 KB Time limit exceeded
31 Halted 0 ms 0 KB -