제출 #1320235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320235		nanaseyuzuki	Bubble Sort 2 (JOI18_bubblesort2)	C++20	38 / 100	9091 ms	1920 KiB

bubblesort2

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, m, q, a[mn], st[mn << 2], lz[mn << 2];
pii v[mn];

void down(int id, int l, int r){
	if(l == r || !lz[id]) return;
	lz[id << 1] += lz[id];
	lz[id << 1 | 1] += lz[id];
	st[id << 1] += lz[id];
	st[id << 1 | 1] += lz[id];
	lz[id] = 0;
}

void update(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st[id] += val;
		lz[id] += val;
		return;
	}
	down(id, l, r);
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, u, v, val);
	update(id << 1 | 1, mid + 1, r, u, v, val);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}

namespace sub2{
	int bit[mn];

	void add(int u, int val){
		while(u){
			bit[u] += val;
			u -= (u & -u);
		}
	}

	int get(int u){
		int r = 0;
		while(u <= m){
			r += bit[u];
			u += (u & -u);
		}
		return r;
	}

	vector <int> sol() {
		vector <int> ans;
		for(int i = 1; i <= q; i++){
			a[v[i].se] = v[i].fi;
			int r = 0;
			for(int i = 1; i <= n; i++){
				add(a[i], 1);
				r = max(r, get(a[i] + 1));
			}
			for(int i = 1; i <= m; i++) bit[i] = 0;
			ans.push_back(r);
		}
		return ans;
	}
}

// ans = max(cnt[i]) với cnt[i] = số cặp nghịch thế của i
vector <int> countScans(vector <int> A, vector <int> X, vector <int> V){
	n = A.size(), q = X.size();
	for(int i = 1; i <= n; i++) a[i] = A[i - 1];
	for(int i = 1; i <= q; i++) v[i] = {V[i - 1], X[i - 1] + 1};

	vector <int> comp;
	for(int i = 1; i <= n; i++) comp.push_back({a[i]});
	for(int i = 1; i <= q; i++) comp.push_back({v[i].fi});
	sort(all(comp)); comp.erase(unique(all(comp)), comp.end());
	
	for(int i = 1; i <= n; i++) a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
	for(int i = 1; i <= q; i++) v[i].fi = lower_bound(all(comp), v[i].fi) - comp.begin() + 1;

	m = comp.size();
	return sub2::sol();
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro

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