Submission #1288860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288860		am_aadvik	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	18 ms	3440 KiB

bubblesort2

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
#include<algorithm>
#include<set>
const int inf = 1e9;
#define SUBMIT 1
using namespace std;
vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);

#ifndef SUBMIT 
#include <cstdio>
#include <cstdlib>
#include <vector>

int readInt() {
	int i;
	if (scanf("%d", &i) != 1) {
		fprintf(stderr, "Error while reading input\n");
		exit(1);
	}
	return i;
}

int main() {
	int N, Q;
	N = readInt();
	Q = readInt();

	std::vector<int> A(N);
	for (int i = 0; i < N; i++)
		A[i] = readInt();

	std::vector<int> X(Q), V(Q);
	for (int j = 0; j < Q; j++) {
		X[j] = readInt();
		V[j] = readInt();
	}

	std::vector<int> res = countScans(A, X, V);

	for (int j = 0; j<int(res.size()); j++)
		printf("%d\n", res[j]);
}
#endif

class segtree {
private:
	vector<int> st, a, lazy;
	int n;
	const int dv = -inf;
	const int ldv = 0;
	void upd(int s, int e, int node, int val) {
		if (val == ldv) return;
		st[node] += (e - s + 1) * val;
	}
	int build(int s, int e, int node) {
		if (s == e) return st[node] = a[s];
		int mid = (s + e) / 2;
		return st[node] = max(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
	}
	int query(int s, int e, int node, int l, int r) {
		if ((l <= s) && (r >= e)) return st[node];
		if ((r < s) || (l > e)) return dv;
		int mid = (s + e) / 2;
		return max(query(s, mid, node * 2, l, r), query(mid + 1, e, node * 2 + 1, l, r));
	}
	void update(int s, int e, int node, int l, int r, int val) {
		if ((r < s) || (l > e)) return;
		if ((l <= s) && (r >= e)) {
			upd(s, e, node, val);
			lazy[node] += val;
			return;
		}
		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
		lazy[node] = ldv;
		update(s, mid, node * 2, l, r, val);
		update(mid + 1, e, node * 2 + 1, l, r, val);
		st[node] = max(st[node * 2], st[node * 2 + 1]);
	}  

public:
	segtree(int N, vector<int> arr) {
		a = arr, n = N;
		st.assign(4 * n, dv);
		lazy.assign(4 * n, ldv);
		build(0, n - 1, 1);
	}
	int query(int l, int r) {
		return query(0, n - 1, 1, l, r);
	}
	void update(int l, int r, int val) {
		update(0, n - 1, 1, l, r, val);
	}
};

void iset(int i, vector<vector<int>> &a, segtree &s) {
	int idx = a[i][1];
	s.update(i, i, idx + inf);
	s.update(i + 1, a.size() - 1, -1);
}
void uset(int i, vector<vector<int>>& a, segtree& s) {
	int idx = a[i][1];
	s.update(i, i, -(idx + inf));
	s.update(i + 1, a.size() - 1, +1);
}
vector<int> countScans(vector<int> a, vector<int> qi, vector<int> qv) {
	int n = a.size(), q = qi.size();
	vector<vector<int>> arr;
	vector<int> pq(q), pa(n);
	segtree s(n + q, vector<int>(n + q, -inf));
	for (int i = 0; i < n; ++i)
		arr.push_back({ a[i], i, -1 });
	for (int i = 0; i < q; ++i)
		arr.push_back({ qv[i], qi[i], i });
	sort(arr.begin(), arr.end());
	for (int i = 0; i < (n + q); ++i)
		if (arr[i][2] != -1) pq[arr[i][2]] = i;
		else pa[arr[i][1]] = i;
	for (int i = 0; i < arr.size(); ++i)
		if (arr[i][2] == -1)
			iset(i, arr, s);
	vector<int> res;
	for (int t = 0; t < q; ++t) {
		int idx = pq[t], i = qi[t], v = qv[t];
		uset(pa[i], arr, s), iset(idx, arr, s);
		int ans = s.query(0, n + q - 1);
		res.push_back(ans);
	}
	return res;;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40