Submission #1212602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212602		catch_me_if_you_can	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	16 ms	2112 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e5+5;
const int INF = 1e9+1e8;

struct l_seg_tree
{
	vector<int> tree;
	vector<int> lazy;
	void init(int n)
	{
		tree.assign(4*n+14, -INF);
		lazy.assign(4*n+14, 0);
		return;
	}
	void push(int id)
	{
		if(lazy[id] == 0)
			return;
		tree[2*id]+=lazy[id]; tree[2*id+1]+=lazy[id];
		lazy[2*id]+=lazy[id]; lazy[2*id+1]+=lazy[id];
		lazy[id] = 0;
		return;
	}
	void upd(int D, int ql, int qr, int id, int l, int r)
	{
		if(qr < l || r < ql)
			return;
		if((ql <= l) && (r <= qr))
		{
			tree[id]+=D;
			lazy[id]+=D;
			return;
		}
		int m = (l+r)/2;
		upd(D, ql, qr, 2*id, l, m);
		upd(D, ql, qr, 2*id+1, m+1, r);
		tree[id] = max(tree[2*id], tree[2*id+1]);
		return;
	}
	int ans()
	{
		return tree[1];
	}
};

l_seg_tree work;

void alive(int x, int N)
{
	work.upd(INF, x, x, 1, 1, N);
	if(x > 1)
		work.upd(1, 1, x-1, 1, 1, N);
	return;
}

void unalive(int x, int N)
{
	work.upd(-INF, x, x, 1, 1, N);
	if(x > 1)
		work.upd(-1, 1, x-1, 1, 1, N);
	return;
}

vector<int> countScans(vector<int> A, vector<int> x, vector<int> v)
{
	int n = A.size();
	vector<in> G;
	for(int i = 0; i < n; i++)
		G.pb({A[i], i});
	for(int i = 0; i < v.size(); i++)
		G.pb({v[i], x[i]});
	sort(G.begin(), G.end());
	vector<in> H; H.pb({-INF, -INF});
	for(auto s: G)
	{
		if(s != H.back())
			H.pb(s);
	}
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)
		a[i] = lower_bound(H.begin(), H.end(), (in){A[i-1], i-1}) - H.begin();
	int q = x.size();
	for(int i = 0; i < q; i++)
		v[i] = lower_bound(H.begin(), H.end(), (in){v[i], x[i]}) - H.begin();
	
	int N = H.size()-1;

	work.init(N);
	for(int i = 1; i <= N; i++)
		work.upd(H[i][1]+1-n, i, i, 1, 1, N);

	for(int i = 1; i <= n; i++)
		alive(a[i], N);


	vector<int> ans(q);

	for(int s = 0; s < q; s++)
	{
		x[s]++;
		unalive(a[x[s]], N);
		a[x[s]] = v[s];
		alive(a[x[s]], N);
		ans[s] = work.ans();	
	}
	return ans;
}

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