oj.uz

Submission #520033

# Submission time Handle Problem Language Result Execution time Memory
520033 2022-01-28T07:51:05 Z akhan42 Bubble Sort 2 (JOI18_bubblesort2) C++17
60 / 100
 9000 ms 46440 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<ii, null_type, less<ii>, 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;


struct Seg {
	int n;
	vi add, mx;

	Seg(int n, vi &vals): n(n) {
		add.assign(4 * n, 0);
		mx.assign(4 * n, 0);

		build(vals);
	}

	void propagate(int v, int tl, int tr) {
		if(tl == tr || add[v] == 0)
			return;

		add[2 * v] += add[v];
		add[2 * v + 1] += add[v];
		mx[2 * v] += add[v];
		mx[2 * v + 1] += add[v];
		add[v] = 0;
	}

	void pull(int v) {
		mx[v] = max(mx[2 * v], mx[2 * v + 1]);
	}

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

		if(tl == tr) {
			mx[v] = vals[tl];
			return;
		}
		int tm = (tl + tr) / 2;

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

		pull(v);
	}

	void update(int l, int r, int val, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r) return;

		if(tl == l && r == tr) {
			add[v] = val;
			mx[v] += val;
			return;
		}
		int tm = (tl + tr) / 2;

		update(l, min(r, tm), val, 2 * v, tl, tm);
		update(max(l, tm + 1), r, val, 2 * v + 1, tm + 1, tr);

		pull(v);
	}

	int query(int l, int r, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r) return -INF;

		if(tl == l && r == tr)
			return mx[v];
		int tm = (tl + tr) / 2;

		int ql = query(l, min(r, tm), 2 * v, tl, tm);
		int qr = query(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);

		return max(ql, qr);
	}

	int get_max() {
		return query(0, n - 1);
	}

	int at(int p) {
		return query(p, p);
	}

	void set(int p, int nval) {
		update(p, p, nval - at(p));
	}
};


struct Seg2 {
	int n;
	vi t;

	Seg2(int n): n(n) {
		t.resize(2 * n);
	}

	void set(int p, int val) {
		for(t[p += n] = val; p > 1; p /= 2)
			t[p >> 1] = t[p] + t[p ^ 1];
	}

	int sum(int l, int r) {
		int res = 0;
		for(l += n, r += n + 1; l < r; l /= 2, r /= 2) {
			if(l & 1) res += t[l++];
			if(r & 1) res += t[--r];
		}
		return res;
	}

	int at(int p) {
		return sum(0, p) - sum(0, p - 1);
	}
};


struct SegSim {
	int n;
	vi t;

	SegSim(int n, vi &vals): n(n) {
		t.resize(n);
		forn(i, n)
			t[i] = vals[i];
	}

	void update(int l, int r, int val) {
		forbn(i, l, r + 1)
			t[i] += val;
	}

	void set(int p, int val) {
		t[p] = val;
	}

	int get_max() {
		int mx = -1000 * 1000 * 1000;
		forn(i, n)
			maxeq(mx, t[i]);
		return mx;
	}
};


vi countScans(vi a, vi xs, vi vs) {
	int n = sz(a);
	int q = sz(xs);

	set<ii> s;
	vii vals;

	forn(i, n) {
		s.insert({a[i], i});
		vals.eb(a[i], i);
	}
	forn(i, q) {
		s.insert({vs[i], xs[i]});
	}
	map<ii, int> p2ind;
	int ct = 0;
	for(ii el: s) {
		p2ind[el] = ct++;
	}

	int N = sz(s);

	sort(all(vals));

	vi seg_vals(N, -INF);
	Seg2 sl(N);

	forn(i, n) {
		int ind = p2ind[vals[i]];
		seg_vals[ind] = vals[i].S - i;
		sl.set(ind, 1);
	}

	SegSim seg(N, seg_vals);
	vi ans(q);

	forn(i, q) {
		int x = xs[i], v = vs[i];

		int ind_fr = p2ind[{a[x], x}];
		int ind_to = p2ind[{v, x}];

		sl.set(ind_fr, 0);
		sl.set(ind_to, 1);

		if(ind_to > ind_fr) {
			seg.update(ind_fr, ind_to, 1);
		}
		if(ind_to < ind_fr) {
			seg.update(ind_to, ind_fr, -1);
		}

		if(ind_to != ind_fr) {
			int rem = x - sl.sum(0, ind_to - 1);
			seg.set(ind_fr, -INF);
			seg.set(ind_to, rem);
		}

		a[x] = v;
		ans[i] = seg.get_max();
//
//		int mx = -1000;
//		forn(x, n) {
//			int ind = p2ind[{a[x], x}];
//			maxeq(mx, x - sl.sum(0, ind - 1));
////			cout << ind << ' ' << sl.sum(0, ind - 1) << endl;
//		}
//		ans[i] = mx;
	}

	return ans;
}


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

	vi xs, vs;
	forn(_, q) {
		int x, v;
		cin >> x >> v;
		xs.pb(x);
		vs.pb(v);
	}

	vi ans = countScans(a, xs, vs);

	for(int a: ans)
		cout << a << endl;

}


//
//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();
//	}
//}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 13 ms 860 KB Output is correct
4 Correct 12 ms 856 KB Output is correct
5 Correct 12 ms 864 KB Output is correct
6 Correct 12 ms 844 KB Output is correct
7 Correct 12 ms 844 KB Output is correct
8 Correct 12 ms 860 KB Output is correct
9 Correct 12 ms 844 KB Output is correct
10 Correct 11 ms 716 KB Output is correct
11 Correct 11 ms 800 KB Output is correct
12 Correct 11 ms 716 KB Output is correct
13 Correct 12 ms 768 KB Output is correct
14 Correct 11 ms 768 KB Output is correct
15 Correct 11 ms 716 KB Output is correct
16 Correct 10 ms 740 KB Output is correct
17 Correct 10 ms 736 KB Output is correct
18 Correct 10 ms 716 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 13 ms 860 KB Output is correct
4 Correct 12 ms 856 KB Output is correct
5 Correct 12 ms 864 KB Output is correct
6 Correct 12 ms 844 KB Output is correct
7 Correct 12 ms 844 KB Output is correct
8 Correct 12 ms 860 KB Output is correct
9 Correct 12 ms 844 KB Output is correct
10 Correct 11 ms 716 KB Output is correct
11 Correct 11 ms 800 KB Output is correct
12 Correct 11 ms 716 KB Output is correct
13 Correct 12 ms 768 KB Output is correct
14 Correct 11 ms 768 KB Output is correct
15 Correct 11 ms 716 KB Output is correct
16 Correct 10 ms 740 KB Output is correct
17 Correct 10 ms 736 KB Output is correct
18 Correct 10 ms 716 KB Output is correct
19 Correct 130 ms 2276 KB Output is correct
20 Correct 161 ms 2748 KB Output is correct
21 Correct 160 ms 2764 KB Output is correct
22 Correct 152 ms 2764 KB Output is correct
23 Correct 154 ms 2480 KB Output is correct
24 Correct 149 ms 2472 KB Output is correct
25 Correct 136 ms 2344 KB Output is correct
26 Correct 135 ms 2344 KB Output is correct
27 Correct 130 ms 2212 KB Output is correct
28 Correct 135 ms 2224 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 4416 KB Output is correct
2 Correct 1869 ms 9648 KB Output is correct
3 Correct 5790 ms 14864 KB Output is correct
4 Correct 5749 ms 15156 KB Output is correct
5 Correct 5529 ms 14964 KB Output is correct
6 Correct 5478 ms 14808 KB Output is correct
7 Correct 5375 ms 14740 KB Output is correct
8 Correct 5401 ms 14816 KB Output is correct
9 Correct 5425 ms 14804 KB Output is correct
10 Correct 2766 ms 9492 KB Output is correct
11 Correct 2788 ms 9608 KB Output is correct
12 Correct 2792 ms 9488 KB Output is correct
13 Correct 2797 ms 9532 KB Output is correct
14 Correct 2814 ms 9544 KB Output is correct
15 Correct 2825 ms 9536 KB Output is correct
16 Correct 2844 ms 9556 KB Output is correct
17 Correct 2833 ms 9544 KB Output is correct
18 Correct 2838 ms 9572 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 13 ms 860 KB Output is correct
4 Correct 12 ms 856 KB Output is correct
5 Correct 12 ms 864 KB Output is correct
6 Correct 12 ms 844 KB Output is correct
7 Correct 12 ms 844 KB Output is correct
8 Correct 12 ms 860 KB Output is correct
9 Correct 12 ms 844 KB Output is correct
10 Correct 11 ms 716 KB Output is correct
11 Correct 11 ms 800 KB Output is correct
12 Correct 11 ms 716 KB Output is correct
13 Correct 12 ms 768 KB Output is correct
14 Correct 11 ms 768 KB Output is correct
15 Correct 11 ms 716 KB Output is correct
16 Correct 10 ms 740 KB Output is correct
17 Correct 10 ms 736 KB Output is correct
18 Correct 10 ms 716 KB Output is correct
19 Correct 130 ms 2276 KB Output is correct
20 Correct 161 ms 2748 KB Output is correct
21 Correct 160 ms 2764 KB Output is correct
22 Correct 152 ms 2764 KB Output is correct
23 Correct 154 ms 2480 KB Output is correct
24 Correct 149 ms 2472 KB Output is correct
25 Correct 136 ms 2344 KB Output is correct
26 Correct 135 ms 2344 KB Output is correct
27 Correct 130 ms 2212 KB Output is correct
28 Correct 135 ms 2224 KB Output is correct
29 Correct 95 ms 4416 KB Output is correct
30 Correct 1869 ms 9648 KB Output is correct
31 Correct 5790 ms 14864 KB Output is correct
32 Correct 5749 ms 15156 KB Output is correct
33 Correct 5529 ms 14964 KB Output is correct
34 Correct 5478 ms 14808 KB Output is correct
35 Correct 5375 ms 14740 KB Output is correct
36 Correct 5401 ms 14816 KB Output is correct
37 Correct 5425 ms 14804 KB Output is correct
38 Correct 2766 ms 9492 KB Output is correct
39 Correct 2788 ms 9608 KB Output is correct
40 Correct 2792 ms 9488 KB Output is correct
41 Correct 2797 ms 9532 KB Output is correct
42 Correct 2814 ms 9544 KB Output is correct
43 Correct 2825 ms 9536 KB Output is correct
44 Correct 2844 ms 9556 KB Output is correct
45 Correct 2833 ms 9544 KB Output is correct
46 Correct 2838 ms 9572 KB Output is correct
47 Execution timed out 9091 ms 46440 KB Time limit exceeded
48 Halted 0 ms 0 KB -