Submission #489643

#	Time	Username	Problem	Language	Result	Execution time	Memory
489643		Killer2501	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1577 ms	250252 KiB

prison

#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cassert>
#define pll pair<int, int>
#define task "test"
#define fi first
#define se second
using namespace std;
using ll = int;
const int  N = 2e6+15;
const ll mod = 998244353;
const ll base = 350;
const ll inf = 1e9;

ll m, n, t, k,ans, tong, a[N], b[N], c[N], d[N], in[N], out[N], cnt, pos[N];
vector<ll> adj[N];
stack<ll> kq;
pll seg[N];
ll pw(ll k, ll n)
{
	ll total = 1;
	for(; n; n >>= 1)
	{
		if(n&1)total = total * k % mod;
		k = k * k % mod;
	}
	return total;
}
struct BIT
{
	ll n;
	vector<ll> fe;
	BIT (ll _n)
	{
		n = _n;
		fe.resize(n+1, 0);
	}
	void clear()
	{
		fill(fe.begin(), fe.end(), 0);
	}
	void add(ll id, ll x)
	{
		for(; id <= n; id += id & -id)fe[id] += x;
	}
	void add(ll l, ll r, ll x)
	{
		if(l > r)return;
		add(l, x);
		add(r+1, -x);
	}
	ll get(ll id)
	{
		ll total = 0;
		for(; id; id -= id & -id)total += fe[id];
		return total;
	}
};
struct suffix
{
	int n, m;
	string s;
	vector<int> cls, p, pn, cnt, rnk, lcp;
	suffix(string _s)
	{
		s = _s + "$";
		n = s.length();
		m = max(n, 256);
		cls.resize(n);
		p.resize(n, 0);
		rnk.resize(n);
		lcp.resize(n);
		pn.resize(n, 0);
		cnt.resize(m+1, 0);
	}
	void fix()
	{
		for(int i = 0; i < n; i ++)++cnt[(int)s[i]-'$'];
		for(int i = 1; i <= m; i ++)cnt[i] += cnt[i-1];
		for(int i = n-1; i >= 0; i --)p[--cnt[(int)s[i]-'$']] = i;
		m = 0;
		cls[p[0]] = m;
		for(int i = 1; i < n; i ++)
		{
			if(s[p[i]] != s[p[i-1]])++m;
			cls[p[i]] = m;
		}
		for(int j = 0; (1<<j) < n; j ++)
		{
			vector<int> cn(n);
			for(int i = 0; i < n; i ++)
			{
				pn[i] = p[i] - (1<<j);
				if(pn[i] < 0)pn[i] += n;
			}
			fill(cnt.begin(), cnt.end(), 0);
			for(int i = 0; i < n; i ++)++cnt[cls[pn[i]]];
			for(int i = 1; i <= m; i ++)cnt[i] += cnt[i-1];
			for(int i = n-1; i >= 0; i --)p[--cnt[cls[pn[i]]]] = pn[i];
			//for(int i = 0; i < n; i ++)cout << p[i] <<" ";
			//cout << '\n';

			m = 0;
			cn[p[0]] = m;
			for(int i = 1; i < n; i ++)
			{
				if(cls[p[i]] != cls[p[i-1]] || cls[(p[i]+(1<<j))%n] != cls[(p[i-1]+(1<<j))%n])
					++m;
				cn[p[i]] = m;
			}
			cls.swap(cn);
		}
		int len = 0;
		for(int i = 0; i < n; i ++)
		{
			//cout << p[i] <<" "<<i<< '\n';
			rnk[p[i]] = i;
		}
		for(int i = 0; i < n; i ++)
		{
			if(rnk[i] == n-1)continue;
			int j = p[rnk[i]+1];
			while(max(i, j)+len < n && s[i+len] == s[j+len])++len;
			lcp[rnk[i]] =  len;
			if(len)--len;
		}

	}
};
string s;
inline bool cmp(const pll& x, const pll& y)
{
    return (x.fi < y.fi) || (x.fi == y.fi && x.se > y.se);
}

    vector<pll> st;
    vector<ll> lazy;
    inline void build(ll id, ll l, ll r)
    {
        lazy[id] = 0;
        if(l == r)
        {
            st[id].fi = 0;
            st[id].se = pos[l];
            return;
        }
        ll mid = (l+r)>>1;
        build(id<<1, l ,mid);
        build(id<<1|1, mid+1, r);
        if(st[id<<1].fi < st[id<<1|1].fi)st[id] = st[id<<1|1];
        else st[id] = st[id<<1];
    }
    inline void down(ll id)
    {
        st[id<<1].fi += lazy[id];
        st[id<<1|1].fi += lazy[id];
        lazy[id<<1] += lazy[id];
        lazy[id<<1|1] += lazy[id];
        lazy[id] = 0;
    }
    inline void update(ll id, ll l, ll r, ll u, ll v, ll x)
    {
        if(u > r || l > v)return;
        if(u <= l && r <= v)
        {
            st[id].fi += x;
            lazy[id] += x;
            return;
        }
        if(lazy[id])down(id);
        ll mid = (l+r)>>1;
        update(id<<1, l, mid, u, v, x);
        update(id<<1|1, mid+1, r, u, v, x);
        if(st[id<<1].fi < st[id<<1|1].fi)st[id] = st[id<<1|1];
        else st[id] = st[id<<1];
    }

inline void dfs(ll u)
{
    in[u] = ++cnt;
    pos[cnt] = u;
    for(ll v: adj[u])dfs(v);
    out[u] = cnt;
}
template<typename T>
inline void read(T&x)
{
    bool Neg=false;
    char c;
    for(c= getchar();c<'0'||c>'9';c=getchar())
        if(c=='-') Neg =!Neg;
    x = c-'0';
    for (c=getchar();c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';
    if(Neg&&x>0) x=-x;
}
bool ok[N];
inline void sol()
{
    read(n);
    read(k);
    read(t);
    for(int i = 1; i <= n; i ++)
    {
        read(a[i]);
        while(!kq.empty() && a[kq.top()]-kq.top() > t-i)kq.pop();
        if(!kq.empty() && a[kq.top()]-kq.top()+i <= t && a[i] > t)
        {
            //cout << kq.back() <<" "<<i-1<<'\n';
            seg[m].fi = kq.top();
            seg[m].se = 1-i;
            ++m;
            ++ans;
        }
        else if(a[i] <= t)++ans;
        kq.push(i);
    }
    sort(seg, seg+m);
    ++ans;

    for(int i = 0, j = 0; i < m; i ++)
    {
        //cout << i <<" "<<seg[i].fi <<" "<<seg[i].se<<'\n';
        while(j && !(seg[j-1].fi <= seg[i].fi && seg[i].se >= seg[j-1].se))j = b[j];
        adj[j].push_back(i+1);
        //cout << j <<" "<<seg[j].fi <<" "<<seg[j].se<<'\n';
        b[i+1] = j;
        j = i+1;
    }
    dfs(0);
    st.resize(cnt*4);
    lazy.resize(cnt*4);
    build(1, 1, cnt);
    for(int i = 1; i <= cnt; i ++)
    {
        t = pos[i];
        update(1, 1, cnt, in[t], out[t], 1);
    }
    //cout << ans << '\n';
    while(k -- > 0)
    {
        if(!ans)break;
        ans -= st[1].fi;
        t = st[1].se;
        //cout << it.st[1].fi <<" "<<it.st[1].se << '\n';
        while(!ok[t])
        {
            ok[t] = true;
            update(1, 1, cnt, in[t], out[t], -1);
            t = b[t];
        }
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:270:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  270 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:271:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  271 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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