Submission #86399

#	Time	Username	Problem	Language	Result	Execution time	Memory
86399		KCSC	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3187 ms	292980 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;

const int DIM = 1000005;
const int INF = 0x3f3f3f3f;

pair<int, int> sgt[DIM * 4];

void updateLazy(int nd, int le, int ri) {
	if (sgt[nd].second) {
		sgt[nd].first += sgt[nd].second;
		if (le != ri) {	
			sgt[nd * 2].second += sgt[nd].second;
			sgt[nd * 2 + 1].second += sgt[nd].second; }
		sgt[nd].second = 0; } }

void update(int nd, int le, int ri, int st, int en, int vl) {
	updateLazy(nd, le, ri);
	if (ri < st or en < le or en < st) {
		return; }
	if (st <= le and ri <= en) {
		sgt[nd].second += vl; updateLazy(nd, le, ri); }
	else {
		int md = (le + ri) / 2;
		update(nd * 2, le, md, st, en, vl);
		update(nd * 2 + 1, md + 1, ri, st, en, vl);
		sgt[nd].first = max(sgt[nd * 2].first, sgt[nd * 2 + 1].first); } }

vector<int> countScans(vector<int> arr, vector<int> pos, vector<int> val) {
	vector<pair<int, int>> crd; vector<int> sol(pos.size());
	for (int i = 0; i < arr.size(); ++i) {	
		crd.push_back(make_pair(arr[i], i)); }
	for (int i = 0; i < pos.size(); ++i) {
		crd.push_back(make_pair(val[i], pos[i])); }
	sort(crd.begin(), crd.end());
	crd.resize(unique(crd.begin(), crd.end()) - crd.begin());
	int n = arr.size(), q = pos.size(), s = crd.size();
	update(1, 0, s - 1, 0, s - 1, -INF);
	for (int i = 0; i < n; ++i) {
		int ps = lower_bound(crd.begin(), crd.end(), make_pair(arr[i], i)) - crd.begin();
		update(1, 0, s - 1, ps, ps, INF + i); update(1, 0, s - 1, ps + 1, s - 1, -1); }
	for (int i = 0; i < q; ++i) {
		int p = pos[i], v = val[i], ps;
		ps = lower_bound(crd.begin(), crd.end(), make_pair(arr[p], p)) - crd.begin();
		update(1, 0, s - 1, ps, ps, -INF - p); update(1, 0, s - 1, ps + 1, s - 1, +1); arr[p] = v;
		ps = lower_bound(crd.begin(), crd.end(), make_pair(arr[p], p)) - crd.begin();
		update(1, 0, s - 1, ps, ps, +INF + p); update(1, 0, s - 1, ps + 1, s - 1, -1); sol[i] = sgt[1].first; }
	return sol; }

#ifdef HOME
int main(void) {
	freopen("bubblesort2.in", "r", stdin);
	freopen("bubblesort2.out", "w", stdout); 
	int n, m; cin >> n >> m;
	vector<int> arr(n), pos(m), val(m), sol;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i]; }
	for (int i = 0; i < m; ++i) {
		cin >> pos[i] >> val[i]; }
	sol = countScans(arr, pos, val);	
	for (int i = 0; i < m; ++i) {
		cout << sol[i] << "\n"; }
	return 0; }
#endif

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < arr.size(); ++i) { 
                  ~~^~~~~~~~~~~~
bubblesort2.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pos.size(); ++i) {
                  ~~^~~~~~~~~~~~

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