Submission #770543

#	Time	Username	Problem	Language	Result	Execution time	Memory
770543		parsadox2	LIS (INOI20_lis)	C++11	100 / 100	1917 ms	163516 KiB

Main

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 10;
int q , ar[maxn] , val[maxn] , ans , fbi[maxn];
vector <pair<int , int>> query;
set <int> st[maxn];
struct nod{
	pair<int , int> mn;
	int lzy;
} tree[maxn << 2];

void Build(int node = 1 , int nl = 0 , int nr = q)
{
	tree[node].lzy = 0;
	if(nl + 1 == nr)
	{
		tree[node].mn.F = ar[nl];  tree[node].mn.S = -nl;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	Build(lc , nl , mid);  Build(rc , mid , nr);
	tree[node].mn = min(tree[lc].mn , tree[rc].mn);
}

void uplzy(int node , int lc , int rc)
{
	if(tree[node].lzy == 0)  return;
	tree[lc].lzy += tree[node].lzy;  tree[rc].lzy += tree[node].lzy;
	tree[lc].mn.F += tree[node].lzy;  tree[rc].mn.F += tree[node].lzy;
	tree[node].lzy = 0;
}

void Rem(int pos , int node = 1 , int nl = 0 , int nr = q)
{
	if(nl + 1 == nr)
	{
		tree[node].mn.F = maxn;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	uplzy(node , lc , rc);
	if(pos < mid)  Rem(pos , lc , nl , mid);
	else Rem(pos , rc , mid , nr);
	tree[node].mn = min(tree[lc].mn , tree[rc].mn);
}

void Add(int pos , int node = 1 , int nl = 0 , int nr = q)
{
	if(nr <= pos)  return;
	if(nl >= pos)
	{
		tree[node].mn.F--;
		tree[node].lzy--;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	Add(pos , lc , nl , mid);  Add(pos , rc , mid , nr);
	tree[node].mn = min(tree[rc].mn , tree[lc].mn);
}

void add(int pos , int ind)
{
	if(st[ind].empty())
	{
		st[ind].insert(pos);
		ans = ind;
		return;
	}
	auto it = st[ind].end();  it--;
	if(*st[ind].begin() < pos)
	{
		if(*it > pos)
		{
			it = st[ind].upper_bound(pos);
			it--;
		}
		if(ar[*it] < ar[pos])
		{
			add(pos , ind + 1);
			return;
		}
		it++;
	}
	else
	{
		it = st[ind].begin();
	}
	vector <int> vec;
	while(it != st[ind].end())
	{
		int now = *it;
		if(ar[now] <= ar[pos])  break;
		it++;
		vec.pb(now);
	}
	for(auto u : vec)
	{
		st[ind].erase(u);
		add(u , ind + 1);
	}
	st[ind].insert(pos);
}

int32_t main()
{
	fast;
	cin >> q;
	for(int i = 0 ; i < q ; i++)  cin >> ar[i] >> val[i];
	Build();
	for(int i = 1 ; i <= q ; i++)
	{
		int pos = -tree[1].mn.S;
		fbi[pos] = i;
		ar[i] = val[pos];
		Rem(pos);
		Add(pos);
	}
	st[0].insert(0);
	for(int i = 0 ; i < q ; i++) 
	{
		add(fbi[i] , 1);
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80