Submission #277091

#	Time	Username	Problem	Language	Result	Execution time	Memory
277091		ChrisT	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	4086 ms	70384 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e6 + 5;
vector<pair<int,int>> xs; int sz;
int getx (const pair<int,int> &x) {return lower_bound(xs.begin(),xs.end(),x) - xs.begin() + 1;}
struct Node {
	int mx,lz;
} tree[MN<<2];
void push_down (int ind, int l, int r) {
	if (!tree[ind].lz) return;
	tree[ind].mx += tree[ind].lz;
	if (l!=r) {
		tree[lc].lz += tree[ind].lz;
		tree[rc].lz += tree[ind].lz;
	}
	tree[ind].lz = 0;
}
void update (int ind, int tl, int tr, int l, int r, int v) {
	push_down(ind,tl,tr);
	if (l > tr || r < tl) return;
	if (l <= tl && tr <= r) {
		tree[ind].lz += v;
		push_down(ind,tl,tr);
		return;
	}
	int mid = (tl + tr) / 2;
	update(lc,tl,mid,l,r,v); update(rc,mid+1,tr,l,r,v);
	tree[ind].mx = max(tree[lc].mx,tree[rc].mx);
}
int query (int ind, int tl, int tr, int l, int r) {
	push_down(ind,tl,tr);
	if (l > tr || r < tl) return INT_MIN;
	if (l <= tl && tr <= r) return tree[ind].mx;
	int mid = (tl + tr) / 2;
	return max(query(lc,tl,mid,l,r),query(rc,mid+1,tr,l,r));
}
int bit[MN];
void u (int x, int v) {
	for (;x<MN;x+=x&-x)
		bit[x] += v;
}
int qu (int x) {
	int ret = 0;
	for (;x;x^=x&-x)
		ret += bit[x];
	return ret;
}
void s (int x, int v) {
	int cur = query(1,1,sz,x,x);
	update(1,1,sz,x,x,v - cur);
}
vector<int> countScans (vector<int> a, vector<int> x, vector<int> v) {
	int n = a.size(), q = x.size(); vector<int> ret(q);
	for (int i = 0; i < n; i++) xs.emplace_back(a[i],i);
	for (int i = 0; i < q; i++) xs.emplace_back(v[i],x[i]);
	sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
	for (Node &nd : tree) nd = {-MN*1000,0};
	sz = xs.size();
	for (int i = 0; i < n; i++) u(getx({a[i],i}),1);
	for (int i = 0; i < n; i++) {
		int pos = getx({a[i],i});
		s(pos,i - qu(pos-1));
	}
	for (int i = 0; i < q; i++) {
		int oldpos = getx({a[x[i]],x[i]});
		s(oldpos,-1e9);
		if (oldpos + 1 <= sz) update(1,1,sz,oldpos+1,sz,1);
		a[x[i]] = v[i];
		int pos = getx({v[i],x[i]});
		u(oldpos,-1); u(pos,1);
		s(pos,x[i] - qu(pos-1));
		if (pos + 1 <= sz) update(1,1,sz,pos+1,sz,-1);
		ret[i] = query(1,1,sz,1,sz);
	}
	return ret;
}

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