Submission #412152

#	Time	Username	Problem	Language	Result	Execution time	Memory
412152		ritul_kr_singh	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1832 ms	61176 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
#include "bubblesort2.h"

struct FenwickTree{
	vector<int> a; int n, s;
	FenwickTree(int N){ a.resize((n=N)+1); }
	void add(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] += v;
	}
	int get(int i){
		for(s=0; i>=1; i-=i&-i) s += a[i];
		return s;
	}
	int get(int l, int r){ return get(r+1) - get(l); }
	int lower(int v){
		int i = 0;
		for(s=1<<20; s; s/=2) if(i+s<=n && a[i+s]<v) v -= a[i+=s];
		return i;
	}
};

const int INF = 1e7;

struct SegmentTree{
	vector<int> a, b; int sz = 1;
	const int ID = -INF;
	SegmentTree(vector<int> &v){
		while(sz < (int)v.size()) sz += sz;
		a.assign(2*sz, ID);
		b.resize(2*sz);
		build(v, 0, 0, sz);
	}
	void build(vector<int> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx < (int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx + rx) / 2;
		build(v, 2*x+1, lx, mx);
		build(v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int v, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = v);
		int mx = (lx + rx) / 2; v -= b[x];
		if(i < mx) update(i, v, 2*x+1, lx, mx);
		else update(i, v, 2*x+2, mx, rx);
		a[x] = b[x] + max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int v){ update(i, v, 0, 0, sz); }
	void rangeAdd(int l, int r, int v, int x, int lx, int rx){
		if(r<=lx || rx<=l) return;
		if(l<=lx && rx<=r){
			a[x] += v;
			b[x] += v;
			return;
		}
		int mx = (lx + rx) / 2;
		rangeAdd(l, r, v, 2*x+1, lx, mx);
		rangeAdd(l, r, v, 2*x+2, mx, rx);
		a[x] = b[x] + max(a[2*x+1], a[2*x+2]);
	}
	void rangeAdd(int l, int r, int v){ rangeAdd(l, r+1, v, 0, 0, sz); }
	int query(){ return a[0]; }
};

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	vector<array<int, 2>> p(A.size()+X.size());

	for(int i=0; i<(int)A.size(); ++i) p[i] = {A[i], i};
	for(int i=0; i<(int)X.size(); ++i) p[i+A.size()] = {V[i], X[i]};
	sort(p.begin(), p.end());

	vector<int> seg(p.size(), -INF), pos(A.size()), res(X.size());
	FenwickTree f(p.size());

	for(int i=0; i<(int)A.size(); ++i){
		array<int, 2> search = {A[i], i};
		pos[i] = lower_bound(p.begin(), p.end(), search) - p.begin();
		f.add(pos[i], 1);
	}
	for(int i=0; i<(int)A.size(); ++i) seg[pos[i]] = i - f.get(0, pos[i] - 1);

	SegmentTree st(seg);

	for(int i=0; i<(int)X.size(); ++i){
		array<int, 2> search = {V[i], X[i]};
		int j = lower_bound(p.begin(), p.end(), search) - p.begin();

		if(pos[X[i]] < j) st.rangeAdd(pos[X[i]], j, 1);
		else st.rangeAdd(j, pos[X[i]], -1);

		f.add(pos[X[i]], -1);
		f.add(j, 1);
		st.update(pos[X[i]], st.ID);
		st.update(pos[X[i]] = j, X[i] - f.get(0, j-1));
		
		res[i] = st.query();
	}

	return res;
}

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