제출 #57637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57637		egorlifar	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	9028 ms	46860 KiB

bubblesort2

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#pragma GCC target("sse4,tune=native")
#pragma GCC optimize("O3","unroll-loops")
#include "bubblesort2.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <deque>
    
     
using namespace std;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define x first
#define y second
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
const string FILENAME = "input";
const int MAXN = 500228;
const int block = 750;


int n;
int id[MAXN * 2];
int who[MAXN * 2];
vector<pair<int, int> > st[MAXN];
vector<int> mod[MAXN];
vector<int> d[MAXN];
int ss[MAXN];
int pos[MAXN * 2];



inline void push(const int &i, const int &v) {
	if (mod[i][v]) {
		d[i][v] += mod[i][v];
		if (v < ss[i]) {
			mod[i][v << 1] += mod[i][v];
			mod[i][(v << 1) + 1] += mod[i][v];
		}
		mod[i][v] = 0;
	}
}


void add(const int &i, int v, int vl, int vr, const int &l, const int &r, const int &x) {
	if (vl > r || vr < l) {
		push(i, v);
		return;
	}
	if (l <= vl && vr <= r) {
		mod[i][v] += x;
		push(i, v);
		return;
	}
	push(i, v);
	int vn = v << 1;
	int vm = (vl + vr) >> 1; 
	add(i, vn, vl, vm, l, r, x);
	add(i, vn + 1, vm + 1, vr, l, r, x);
	d[i][v] = max(d[i][vn], d[i][vn + 1]);
}


bool need = false;


void add(int i) {
	int cnt = 1000000000;
	for (int j = i - 1; j >= i - (i % block); j--) {
		if (who[id[j]] > who[id[i]]) {
			cnt++;
		}
	}
	int ids = i / block;
	add((ids), 1, 1, ss[(ids)], pos[id[i]], pos[id[i]], cnt);
	for (int j = (ids) + 1; j <= (n - 1) / block; j++) {
		int t = lower_bound(all(st[j]), make_pair(who[id[i]], 0)) - st[j].begin();
		if (t) {
			add(j, 1, 1, ss[j], 1, t, 1);
		}
	}
}



int res[MAXN * 2];


void deladd(int i, int nid) {
	int ids = i / block;
	int bmax = min(i - (i % block) + block - 1, n - 1);
	for (int j = 1; j < 2 * ss[ids]; j++) {
		push(ids, j);
	}
	for (int j = 0; j < sz(st[ids]); j++) {
		res[st[ids][j].second] = d[ids][ss[ids] + j];
	}
	st[ids].pb({who[nid], nid});
	int cur = sz(st[ids]) - 1;
	while (cur && st[ids][cur] < st[ids][cur - 1]) {
		swap(st[ids][cur], st[ids][cur - 1]);
		cur--;
	}
	for (int j = i + 1; j <= bmax; j++) {
		int cnt = 0;
		if (who[id[j]] < who[id[i]]) {
			cnt--;
		}
		if (who[id[j]] < who[nid]) {
			cnt++;
		}
		if (cnt != 0) {
			res[id[j]] += cnt;
		}
	}
	int cnt = 0;
	for (int j = i - 1; j >= i - (i % block); j--) {
		if (who[id[j]] > who[nid]) {
			cnt++;
		}
	}
	res[nid] = cnt;
	for (int j = (ids) - 1; j >= 0; j--) {
		int t = upper_bound(all(st[j]), make_pair(who[nid], 1000000000)) - st[j].begin();
		res[nid] += sz(st[j]) - t;
	}
	int pos = 0;
	for (int j = 0; j < sz(st[ids]); j++) {
		if (st[ids][j].second == id[i]) {
			swap(st[ids][j], st[ids].back());
			pos = j;
			break;
		}
	}
	st[ids].pop_back();
	while (pos < sz(st[ids]) - 1) {
		swap(st[ids][pos], st[ids][pos + 1]);
		pos++;
	}
	for (int j = 0; j < sz(st[ids]); j++) {
		d[ids][ss[ids] + j] = res[st[ids][j].second];
		mod[ids][ss[ids] + j] = 0;
	}
	for (int j = ss[ids] - 1; j >= 1; j--) {
		d[ids][j] = max(d[ids][j * 2], d[ids][j * 2 + 1]);
		mod[ids][j] = 0;
	}
	for (int j = (ids) + 1; j <= (n - 1) / block; j++) {
		int t = lower_bound(all(st[j]), make_pair(who[id[i]], 0)) - st[j].begin();
		int t1 = lower_bound(all(st[j]), make_pair(who[nid], 0)) - st[j].begin();
		//1 - t === -1
		//1 - t1 == +1;
		if (t != t1) {
			if (t == 0 && t1 != 0) {
				add(j, 1, 1, ss[j], 1, t1, 1);
			} else if (t1 == 0 && t != 0) {
				add(j, 1, 1, ss[j], 1, t, -1);
			} else {
				if (t < t1) {
					add(j, 1, 1, ss[j], t + 1, t1, 1);
				} else {
					add(j, 1, 1, ss[j], t1 + 1, t, -1);
				}
			}
		}
	}
}




std::vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n = sz(A);
	for (int i = 0; i < n; i++) {
		st[(i / block)].pb({A[i], i});
		id[i] = i;
		who[i] = A[i];
	}
	vector<int> answer;
	for (int i = 0; i <= (n - 1) / block; i++) {
		sort(all(st[i]));
		ss[i] = 1;
		while (ss[i] < sz(st[i])) {
			ss[i] <<= 1;
		}
		d[i].resize(2 * ss[i]);
		mod[i].resize(2 * ss[i]);
		for (int j = 0; j < sz(st[i]); j++) {
			pos[st[i][j].second] = j + 1;
		}
		for (int j = 0; j < 2 * ss[i]; j++) {
			d[i][j] = -1e9;
			mod[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		add(i);
	}
	need = true;
	//exit(0);
	for (int i = 0; i < sz(X); i++) {
		who[n + i] = V[i];
		deladd(X[i], n + i);
		id[X[i]] = n + i;
		int res = 0;
		for (int j = 0; j <= (n - 1) / block; j++) {
			chkmax(res, d[j][1] + mod[j][1]);
		}
		answer.pb(res);
	}
	return answer;
}

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