oj.uz

Submission #99636

# Submission time Handle Problem Language Result Execution time Memory
99636 2019-03-06T02:02:42 Z jasony123123 Bubble Sort 2 (JOI18_bubblesort2) C++11
60 / 100
 9000 ms 11000 KB 
#define _CRT_SECURE_NO_WARNINGS
//#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/***************************JOI Open 18 - bubblesort***********************************/

const int inf = 1 << 20;
struct LazySegTree {
	int sz;
	v<int> a;
	
	void init(int n, int val) {
		a = v<int>(n, val);
		sz = n;
	}
	int query() {
		int ans = 0;
		FOR(i, 0, sz) maxx(ans, a[i]);
		return ans;
	}
	void update(int lo, int hi, int val) {
		FORE(i, lo, hi) a[i] += val;
	}
};

v<int> countScans(v<int> A, v<int> X, v<int> V) {
	int n = A.size(), q = X.size();

	// compress
	v<pii> dat;
	dat.reserve(n + q);
	FOR(i, 0, n) dat.push_back({ A[i], i });
	FOR(i, 0, q) dat.push_back({ V[i], X[i] });
	sort(all(dat));
	dat.resize(unique(all(dat)) - dat.begin());
	FOR(i, 0, n) A[i] = lower_bound(all(dat), mp(A[i], i)) - dat.begin();
	FOR(i, 0, q) V[i] = lower_bound(all(dat), mp(V[i], X[i])) - dat.begin();

	// init
	LazySegTree tree;
	tree.init(dat.size(), -inf);
	FOR(i, 0, n) {
		tree.update(A[i] + 1, tree.sz - 1, -1);
		tree.update(A[i], A[i], inf+i);
	}

	// process q
	v<int> ans(q);
	FOR(i, 0, q) {
		int pos = X[i];
		int _new = V[i];
		int _old = A[pos];

		tree.update(_old, _old, -inf - pos);
		tree.update(_new, _new, inf + pos);
		if (_new < _old)
			tree.update(_new + 1, _old, -1);
		else if (_new > _old)
			tree.update(_old + 1, _new, +1);

		A[pos] = _new;
		ans[i] = tree.query();
	}

	return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 14 ms 512 KB Output is correct
4 Correct 13 ms 512 KB Output is correct
5 Correct 14 ms 492 KB Output is correct
6 Correct 13 ms 384 KB Output is correct
7 Correct 16 ms 512 KB Output is correct
8 Correct 13 ms 384 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 16 ms 512 KB Output is correct
11 Correct 14 ms 512 KB Output is correct
12 Correct 13 ms 384 KB Output is correct
13 Correct 14 ms 512 KB Output is correct
14 Correct 15 ms 512 KB Output is correct
15 Correct 13 ms 484 KB Output is correct
16 Correct 16 ms 384 KB Output is correct
17 Correct 11 ms 512 KB Output is correct
18 Correct 13 ms 384 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 14 ms 512 KB Output is correct
4 Correct 13 ms 512 KB Output is correct
5 Correct 14 ms 492 KB Output is correct
6 Correct 13 ms 384 KB Output is correct
7 Correct 16 ms 512 KB Output is correct
8 Correct 13 ms 384 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 16 ms 512 KB Output is correct
11 Correct 14 ms 512 KB Output is correct
12 Correct 13 ms 384 KB Output is correct
13 Correct 14 ms 512 KB Output is correct
14 Correct 15 ms 512 KB Output is correct
15 Correct 13 ms 484 KB Output is correct
16 Correct 16 ms 384 KB Output is correct
17 Correct 11 ms 512 KB Output is correct
18 Correct 13 ms 384 KB Output is correct
19 Correct 129 ms 1016 KB Output is correct
20 Correct 159 ms 1016 KB Output is correct
21 Correct 158 ms 896 KB Output is correct
22 Correct 163 ms 1020 KB Output is correct
23 Correct 153 ms 1016 KB Output is correct
24 Correct 144 ms 952 KB Output is correct
25 Correct 145 ms 892 KB Output is correct
26 Correct 169 ms 904 KB Output is correct
27 Correct 146 ms 896 KB Output is correct
28 Correct 136 ms 888 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 1064 KB Output is correct
2 Correct 2160 ms 2296 KB Output is correct
3 Correct 6030 ms 3484 KB Output is correct
4 Correct 6223 ms 3480 KB Output is correct
5 Correct 5765 ms 3564 KB Output is correct
6 Correct 5944 ms 3568 KB Output is correct
7 Correct 5613 ms 3560 KB Output is correct
8 Correct 6105 ms 3480 KB Output is correct
9 Correct 5861 ms 3504 KB Output is correct
10 Correct 2908 ms 3448 KB Output is correct
11 Correct 2826 ms 3456 KB Output is correct
12 Correct 2863 ms 3320 KB Output is correct
13 Correct 2892 ms 3448 KB Output is correct
14 Correct 2902 ms 3452 KB Output is correct
15 Correct 3012 ms 3312 KB Output is correct
16 Correct 2850 ms 3500 KB Output is correct
17 Correct 2867 ms 3472 KB Output is correct
18 Correct 2900 ms 3448 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 14 ms 512 KB Output is correct
4 Correct 13 ms 512 KB Output is correct
5 Correct 14 ms 492 KB Output is correct
6 Correct 13 ms 384 KB Output is correct
7 Correct 16 ms 512 KB Output is correct
8 Correct 13 ms 384 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 16 ms 512 KB Output is correct
11 Correct 14 ms 512 KB Output is correct
12 Correct 13 ms 384 KB Output is correct
13 Correct 14 ms 512 KB Output is correct
14 Correct 15 ms 512 KB Output is correct
15 Correct 13 ms 484 KB Output is correct
16 Correct 16 ms 384 KB Output is correct
17 Correct 11 ms 512 KB Output is correct
18 Correct 13 ms 384 KB Output is correct
19 Correct 129 ms 1016 KB Output is correct
20 Correct 159 ms 1016 KB Output is correct
21 Correct 158 ms 896 KB Output is correct
22 Correct 163 ms 1020 KB Output is correct
23 Correct 153 ms 1016 KB Output is correct
24 Correct 144 ms 952 KB Output is correct
25 Correct 145 ms 892 KB Output is correct
26 Correct 169 ms 904 KB Output is correct
27 Correct 146 ms 896 KB Output is correct
28 Correct 136 ms 888 KB Output is correct
29 Correct 321 ms 1064 KB Output is correct
30 Correct 2160 ms 2296 KB Output is correct
31 Correct 6030 ms 3484 KB Output is correct
32 Correct 6223 ms 3480 KB Output is correct
33 Correct 5765 ms 3564 KB Output is correct
34 Correct 5944 ms 3568 KB Output is correct
35 Correct 5613 ms 3560 KB Output is correct
36 Correct 6105 ms 3480 KB Output is correct
37 Correct 5861 ms 3504 KB Output is correct
38 Correct 2908 ms 3448 KB Output is correct
39 Correct 2826 ms 3456 KB Output is correct
40 Correct 2863 ms 3320 KB Output is correct
41 Correct 2892 ms 3448 KB Output is correct
42 Correct 2902 ms 3452 KB Output is correct
43 Correct 3012 ms 3312 KB Output is correct
44 Correct 2850 ms 3500 KB Output is correct
45 Correct 2867 ms 3472 KB Output is correct
46 Correct 2900 ms 3448 KB Output is correct
47 Execution timed out 9028 ms 11000 KB Time limit exceeded
48 Halted 0 ms 0 KB -