Submission #776632

#	Time	Username	Problem	Language	Result	Execution time	Memory
776632		ymm	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9068 ms	2124 KiB

bubblesort2

#include "bubblesort2.h"

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 1'000'010;

namespace seg {
	int a[N];
	void add(int l, int r, int x) {
		Loop (i,l,r)
			a[i] += x;
	}
	int get() {
		int ans = 0;
		Loop (i,0,N)
			ans = max(ans, a[i]);
		return ans;
	}
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	int n = A.size();
	int q = X.size();
	vector<pii> cmp;
	Loop (i,0,n)
		cmp.push_back({A[i], i});
	Loop (i,0,q)
		cmp.push_back({V[i], X[i]});
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	Loop (i,0,n)
		A[i] = lower_bound(cmp.begin(), cmp.end(), pii{A[i], i}) - cmp.begin();
	Loop (i,0,q)
		V[i] = lower_bound(cmp.begin(), cmp.end(), pii{V[i], X[i]}) - cmp.begin();
	Loop (i,0,n) {
		seg::add(A[i], A[i]+1, i);
		seg::add(A[i]+1, cmp.size(), -1);
	}
	vector<int> ans;
	Loop (j,0,q) {
		int i = X[j];
		seg::add(A[i], A[i]+1, -i);
		seg::add(A[i]+1, cmp.size(), 1);
		A[i] = V[j];
		seg::add(A[i], A[i]+1, i);
		seg::add(A[i]+1, cmp.size(), -1);
		ans.push_back(seg::get());
	}
	return ans;
}

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