Submission #1081036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081036		ten_xd	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9037 ms	6100 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int N = 5e5+5, INF = 2e9+54321;
const ull INF_L = (ll)2e18+54321;

int n,q,base,rozmiar_drzewa;
int B[N], XX[N], YY[N];
vector<int> tree;

void update(int v)
{
	v += base, tree[v] += 1, v /= 2;
	while(v > 0) tree[v] = tree[v*2] + tree[v*2+1], v /= 2;
}

int query(int l, int p)
{
	l = l + base - 1, p = p + base + 1;
	int res = 0;
	while(l/2 != p/2)
	{
		if(l % 2 == 0) res += tree[l+1];
		if(p % 2 == 1) res += tree[p-1];
		l /= 2, p /= 2;
	}
	return res;
}

vector<int> solve()
{
	vector<int> res;
	map<int,int> M;
	rep(i,n) M[B[i]] = -1;
	rep(i,q) M[YY[i]] = -1;
	int cnt = -1;
	for(auto it = M.begin(); it != M.end(); ++it) it->second = ++cnt;

	base = 1;
	while(base <= n+q+50) base *= 2;
	rozmiar_drzewa = base * 2;

	rep(i,n) B[i] = M[B[i]];
	rep(z,q)
	{
		B[XX[z]] = M[YY[z]];
		tree.assign(rozmiar_drzewa,0);

		int wyn = 0;

		rep(i,n)
		{
			wyn = max(wyn,query(B[i]+1,n+q+3));
			update(B[i]);
		}

		res.pb(wyn);
	}

	return res;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V)
{
	n = (int)A.size(), q = (int)X.size();
	rep(i,n) B[i] = A[i];
	rep(i,q) XX[i] = X[i], YY[i] = V[i];

	return solve();
}

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