Submission #485626

#	Time	Username	Problem	Language	Result	Execution time	Memory
485626		pooyashams	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1605 ms	318220 KiB

prison

#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cassert>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e6+10;

int n, D, T;

vector<int> kids[maxn];
int stme[maxn];
int tmi[maxn];
int frit[maxn];
int par[maxn];
int init[maxn];
bool vis[maxn];
int tin[maxn];
int tout[maxn];
int inord[maxn];
int timer = 0;

struct seg
{
	int l, r;
	inline bool operator<(seg& b)
	{
		return l < b.l  or (l == b.l and r > b.r);
	}
	inline bool in(seg& b)
	{
		return b.l <= l and r <= b.r;
	}
} segs[maxn];

void dfs(int v, int h)
{
	init[v] = h;
	tin[v] = timer++;
	inord[tin[v]] = v;
	for(int u: kids[v])
		dfs(u, h+1);
	tout[v] = timer;
}

struct lzst
{
	vector<int> vals; // max
	vector<int> vidx; // max index
	vector<int> lazy;
	int n;
	lzst(int len)
	{
		vals = vector<int>(len * 4, 0);
		vidx = vector<int>(len * 4, 0);
		lazy = vector<int>(len * 4, 0);
		n = len;
		build(0, len, 1);
	}
	inline void upd(int v)
	{
		vals[v] = max(vals[2*v], vals[2*v+1]);
		if(vals[v] == vals[2*v])
			vidx[v] = vidx[2*v];
		else
			vidx[v] = vidx[2*v+1];
	}
	inline void put(int x, int v)
	{
		vals[v] += x;
		lazy[v] += x;
	}
	inline void shift(int v)
	{
		if(lazy[v] == 0) return;
		put(lazy[v], 2*v);
		put(lazy[v], 2*v+1);
		lazy[v] = 0;
	}
	void build(int l, int r, int v)
	{
		if(r - l == 1)
		{
			vals[v] = init[inord[l]];
			vidx[v] = inord[l];
			lazy[v] = 0;
			return;
		}
		int m = (l+r) / 2;
		build(l, m, 2*v);
		build(m, r, 2*v+1);
		upd(v);
	}
	void _add(int l, int r, int s, int e, int x, int v)
	{
		if(e <= l or r <= s) return;
		if(s <= l and r <= e) return put(x, v);
		int m = (l+r) / 2;
		shift(v);
		_add(l, m, s, e, x, 2*v);
		_add(m, r, s, e, x, 2*v+1);
		upd(v);
	}
	inline void add(int s, int e, int x)
	{
		_add(0, n, s, e, x, 1);
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> D >> T;
	stack<int> st;
	int scnt = 0;
	segs[scnt++] = {0, n};
	int rem = n+1;
	for(int i = 0; i < n; i++)
	{
		cin >> stme[i];
		tmi[i] = stme[i] - i;
		st.push(i);
		while(!st.empty() and tmi[st.top()] > T-i)
			st.pop();
		if(st.empty())
		{
			frit[i] = i;
			rem--;
		}
		else
			frit[i] = st.top();
		if(frit[i] != i)
			segs[scnt++] = {frit[i], i};
		//cerr << "frit[" << i << "]: " << frit[i] << endl;
	}
	sort(segs, segs+scnt);
	//for(int i = 0; i < scnt; i++) cerr << i << ": " << segs[i].l << " " << segs[i].r << endl; cerr << endl;
	int lst = 0;
	par[0] = -1;
	for(int i = 1; i < scnt; i++)
	{
		while(!segs[i].in(segs[lst]))
			lst = par[lst];
		par[i] = lst;
		kids[lst].push_back(i);
		lst = i;
		//cerr << "par[" << i << "]: " << par[i] << endl;
	}
	dfs(0, 1);
	//for(int i = 0; i < scnt; i++) assert(tin[i] == i);
	lzst mf(scnt);
	//cerr << rem << endl;
	//for(int i = 0; i < 15; i++) cerr << mf.vals[i] << " "; cerr << endl << endl;
	while(D--)
	{
		int v = mf.vidx[1];
		//cerr << v << endl;
		while(v != -1 and !vis[v])
		{
			mf.add(tin[v], tout[v], -1);
			vis[v] = true;
			rem--;
			v = par[v];
		}
	}
	cout << rem << endl;
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 20 / 20