Submission #202097

#	Time	Username	Problem	Language	Result	Execution time	Memory
202097		wilwxk	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4720 ms	133064 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
 
struct node {
	int mx, qtd, lz;
};
 
const int MAXN = 1e6+6;
const int INF = 5e7;
map<int, int> mp;
vector<int> ans;
int pos[MAXN];
int mpcnt[MAXN], mpaux[MAXN];
node seg[MAXN*4];
int n, q, mpn;
 
void refresh(int sind, int l, int r) {
	if(!seg[sind].lz) return;
	seg[sind].mx += seg[sind].lz;
	int val = seg[sind].lz;
	seg[sind].lz = 0;
	if(l == r) return;
	int e = sind*2; int d = e+1;
	seg[e].lz += val;
	seg[d].lz += val;
}
 
int query(int sind, int l, int r, int ql, int qr) {
	refresh(sind, l, r);
	if(ql > r || qr < l) return 0;
	if(ql <= l && qr >= r) return seg[sind].qtd;
	int m = (l+r)/2;
	int e = sind*2; int d = e+1;
	return query(e, l, m, ql, qr) + query(d, m+1, r, ql, qr);
}
 
void update1(int sind, int l, int r, int qind, int val) {
	refresh(sind, l, r);
	if(qind > r || qind < l) return;
	if(l == r) {
		seg[sind].mx = val;
		seg[sind].qtd = val != -INF;
		return;
	}
	int m = (l+r)/2;
	int e = sind*2; int d = e+1;
	update1(e, l, m, qind, val);
	update1(d, m+1, r, qind, val);
	seg[sind].mx = max(seg[e].mx, seg[d].mx);
	seg[sind].qtd = seg[e].qtd + seg[d].qtd;
}
 
void update2(int sind, int l, int r, int ql, int qr, int val) {
	refresh(sind, l, r);
	if(ql > r || qr < l) return;
	if(ql <= l && qr >= r) {
		seg[sind].lz += val;
		refresh(sind, l, r);
		return;
	}
	int m = (l+r)/2;
	int e = sind*2; int d = e+1;
	update2(e, l, m, ql, qr, val);
	update2(d, m+1, r, ql, qr, val);
	seg[sind].mx = max(seg[e].mx, seg[d].mx);
	seg[sind].qtd = seg[e].qtd + seg[d].qtd;
}
 
vector<int> countScans(vector<int> input, vector<int> qi, vector<int> qv){
	n = input.size();
	q = qi.size();
	
	for(int val : input) mp[val] = 1;
	for(int val : qv) mp[val] = 1;
	for(auto &mit : mp) mit.second = ++mpn;
	for(int &val : input) val = mp[val], mpcnt[val]++;
	for(int &val : qv) val = mp[val], mpcnt[val]++;
	for(int i = 2; i <= mpn; i++) mpcnt[i] += mpcnt[i-1];
	mpn = mpcnt[mpn];
 
	for(int i = 1; i <= 4*mpn; i++) seg[i].mx = -INF;
	for(int i = 0; i < n; i++) {
		int val = input[i];
		mpaux[val]++;
		pos[i] = mpcnt[val-1]+mpaux[val];
		int presum = query(1, 1, mpn, 1, mpcnt[val]);
		update2(1, 1, mpn, mpcnt[val-1]+1, mpn, -1);
		update1(1, 1, mpn, pos[i], i-presum);
	}
	// printf("mx %d\n", seg[1].mx);
	for(int i = 0; i < q; i++) {
		int ind = qi[i], val = qv[i];
		update2(1, 1, mpn, mpcnt[input[ind]-1]+1, mpn, 1);
		update1(1, 1, mpn, pos[ind], -INF);
		input[ind] = val;
		mpaux[val]++;
		pos[ind] = mpcnt[val-1]+mpaux[val];
		int presum = query(1, 1, mpn, 1, mpcnt[val]);
		// printf("%d: %d - %d %d >> %d\n", ind, val, pos[ind], presum, ind-presum);
		update2(1, 1, mpn, mpcnt[val-1]+1, mpn, -1);
		update1(1, 1, mpn, pos[ind], ind-presum);
		ans.push_back(seg[1].mx);
	}
 
	return ans;
}

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