Submission #503348

#	Time	Username	Problem	Language	Result	Execution time	Memory
503348		amunduzbaev	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2943 ms	104148 KiB

bubblesort2

#include "bubblesort2.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
//~ #define int long long

const int N = 1e6 + 5;

struct ST{
	int tree[1 << 21], p[1 << 21];
	
	void push(int x, int lx, int rx){
		if(lx == rx || !p[x]) return;
		tree[x<<1] += p[x], tree[x<<1|1] += p[x];
		p[x<<1] += p[x], p[x<<1|1] += p[x];
		p[x] = 0;
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x] += v, p[x] += v;
			return;
		} push(x, lx, rx);
		int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x<<1), add(l, r, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
}tree;

//~ #define i32 int32_t

vector<int> countScans(vector<int> X, vector<int> in, vector<int> Y){
	vector<long long> a, val;
	for(auto x : X) a.push_back(x);
	for(auto x : Y) val.push_back(x);
	int n = (int)a.size(), q = (int)in.size();
	map<long long, int> mm;
	
	for(int i=0;i<n;i++) a[i] = a[i] * 1ll * n + i, mm[a[i]];
	for(int i=0;i<q;i++) val[i] = val[i] * 1ll * n + in[i], mm[val[i]];
	
	{
		int in = 0;
		for(auto& x : mm) x.second = in++;
		for(int i=0;i<n;i++) a[i] = mm[a[i]];
		for(int i=0;i<q;i++) val[i] = mm[val[i]];
	}
	
	for(int i=0;i<n;i++) tree.add(a[i], a[i], i), tree.add(a[i] + 1, N, -1);
	vector<int> res;
	for(int j=0;j<q;j++){
		int i = in[j], v = val[j];
		tree.add(a[i] + 1, N, +1);
		tree.add(a[i], a[i], -i);
		a[i] = v;
		tree.add(a[i], a[i], i);
		tree.add(a[i] + 1, N, -1);
		
		res.push_back(tree.tree[1]);
	} return res;
}

/*

4 2
1 2 3 4
0 3
2 1

*/

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