Submission #753405

#	Time	Username	Problem	Language	Result	Execution time	Memory
753405		MetalPower	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2491 ms	55388 KiB

bubblesort2

#include "bubblesort2.h"

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

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 1e6 + 10;

struct segtree{
	int st[MX << 2], lz[MX << 2];

	void prop(int id, int l, int r){
		if(lz[id] == 0) return;
		st[id] += lz[id];
		if(l != r){
			lz[id << 1] += lz[id];
			lz[id << 1|1] += lz[id];
		}
		lz[id] = 0;
	}

	void upd(int id, int from, int to, int l, int r, int v){
		if(to < from) return;
		// if(id == 1) cout << "update " << from << " to " << to << " value " << v << '\n';
		prop(id, l, r);
		if(r < from || l > to) return;
		if(from <= l && r <= to){
			lz[id] += v;
			prop(id, l, r);
		}else{
			int mid = l + r >> 1;
			upd(id << 1, from, to, l, mid, v);
			upd(id << 1|1, from, to, mid + 1, r, v);
			st[id] = max(st[id << 1], st[id << 1|1]);
		}
	}

	int que(int id, int from, int to, int l, int r){
		prop(id, l, r);
		if(r < from || l > to) return 0;
		if(from <= l && r <= to){
			return st[id];
		}else{
			int mid = l + r >> 1;
			return max(
				que(id << 1, from, to, l, mid),
				que(id << 1|1, from, to, mid + 1, r)
			);
		}
	}
} S;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	
	vector<pii> vec;
	for(int i = 0; i < (int) A.size(); i++) vec.push_back({A[i], i});
	for(int i = 0; i < (int) X.size(); i++) vec.push_back({V[i], X[i]});

	sort(vec.begin(), vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());

	int M = vec.size();

	for(int i = 0; i < (int) A.size(); i++){
		int idx = lower_bound(vec.begin(), vec.end(), make_pair(A[i], i)) - vec.begin();
		S.upd(1, idx, idx, 0, M - 1, i);
		S.upd(1, idx + 1, M - 1, 0, M - 1, -1);
	}

	vector<int> pos = A, ans;

	for(int i = 0; i < (int) X.size(); i++){
		int prev_idx = lower_bound(vec.begin(), vec.end(), make_pair(pos[X[i]], X[i])) - vec.begin();
		int curr_idx = lower_bound(vec.begin(), vec.end(), make_pair(V[i], X[i])) - vec.begin();
		S.upd(1, prev_idx, prev_idx, 0, M - 1, -X[i]);
		S.upd(1, prev_idx + 1, M - 1, 0, M - 1, 1);
		S.upd(1, curr_idx, curr_idx, 0, M - 1, X[i]);
		S.upd(1, curr_idx + 1, M - 1, 0, M - 1, -1);
		ans.push_back(S.que(1, 0, M - 1, 0, M - 1));
		pos[X[i]] = V[i];
	}

	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In member function 'void segtree::upd(int, int, int, int, int, int)':
bubblesort2.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |    int mid = l + r >> 1;
      |              ~~^~~
bubblesort2.cpp: In member function 'int segtree::que(int, int, int, int, int)':
bubblesort2.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |    int mid = l + r >> 1;
      |              ~~^~~

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