Submission #776634

#	Time	Username	Problem	Language	Result	Execution time	Memory
776634		ymm	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1509 ms	53364 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 t[4*N];
	int mx[4*N];
	void add(int l, int r, int x, int i, int b, int e) {
		if (l <= b && e <= r) {
			t[i] += x;
			mx[i] += x;
			return;
		}
		if (r <= b || e <= l)
			return;
		add(l, r, x, 2*i+1, b, (b+e)/2);
		add(l, r, x, 2*i+2, (b+e)/2, e);
		mx[i] = t[i] + max(mx[2*i+1], mx[2*i+2]);
	}
	void add(int l, int r, int x) { add(l, r, x, 0, 0, N); }
	int get() { return mx[0]; }
}

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: 22 / 22
• Subtask 4: 40 / 40