/ WOJ /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Wrong Answer 成绩取消 0ms 0 Bytes

代码

#include <bits/extc++.h>
#define endl '\n'
typedef long long ll;
#define int ll
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

constexpr int inf = 0x3f3f3f3f3f3f3f3f;

mt19937 rand_get(chrono::steady_clock::now().time_since_epoch().count());

int k4p;

struct ly
{
	ly *lp = nullptr, *rp = nullptr;
	int key, val;
	int cost = 0, scs = 0;
	uint32_t pri;
	ly() = default;
	ly(const int kkey, const int vval) : key(kkey), val(vval), pri(rand_get())
	{
		const int gap_len = val - key + 1;
		cost = gap_len > 0 ? (gap_len + k4p - 1) / k4p : 0;
		scs = cost;
	}
};

constexpr int mxnn = 4e6;
ly np[mxnn];
int npi;

ly* nly(const int key, const int val)
{
	np[npi] = ly(key, val);
	return &np[npi++];
}

void pull(ly* t)
{
	if (!t)
	{
		return;
	}
	const int l_sum = t->lp ? t->lp->scs : 0;
	const int r_sum = t->rp ? t->rp->scs : 0;
	t->scs = l_sum + r_sum + t->cost;
}

void split(ly* t, const int key, ly*& l, ly*& r)
{
	if (!t)
	{
		l = r = nullptr;
		return;
	}
	if (t->key < key)
	{
		split(t->rp, key, t->rp, r);
		l = t;
	}
	else
	{
		split(t->lp, key, l, t->lp);
		r = t;
	}
	pull(t);
}

ly* merge(ly* l, ly* r)
{
	if (!l || !r)
	{
		return l ? l : r;
	}
	if (l->pri > r->pri)
	{
		l->rp = merge(l->rp, r);
		pull(l);
		return l;
	}
	r->lp = merge(l, r->lp);
	pull(r);
	return r;
}

void insert(ly*& t, ly* itt)
{
	if (!t || itt == nullptr)
	{
		if (itt)
		{
			t = itt;
		}
		pull(t);
		return;
	}
	ly *t1, *t2;
	split(t, itt->key, t1, t2);
	t = merge(merge(t1, itt), t2);
}

pair<int, int> fbri(ly* t, int bud)
{
	if (!t)
	{
		return {-1, bud};
	}
	const int lsm = t->lp ? t->lp->scs : 0;
	if (bud < lsm)
	{
		return fbri(t->lp, bud);
	}
	bud -= lsm;
	if (bud < t->cost)
	{
		return {t->key, bud};
	}
	bud -= t->cost;
	return fbri(t->rp, bud);
}

void Main()
{
	int n, m;
	cin >> n >> m >> k4p;
	vector<int> a(n);
	for (int& x : a)
	{
		cin >> x;
	}
	npi = 0;
	auto gprt = nly(0, inf);
	for (int i = 0; i < n; ++i)
	{
		const int cl = max(0ll, a[i] - k4p + 1);
		const int cr = a[i];
		ly *lp, *mp, *rp;
		split(gprt, cl, lp, mp);
		split(mp, cr + 1, mp, rp);
		vector<pair<int, int>> ad2;
		if (lp)
		{
			const ly* tmp = lp;
			while (tmp->rp)
			{
				tmp = tmp->rp;
			}
			if (tmp->val >= cl)
			{
				ly *curl, *i2p;
				split(lp, tmp->key, curl, i2p);
				if (i2p->key < cl)
				{
					ad2.emplace_back(i2p->key, cl - 1);
				}
				if (i2p->val > cr)
				{
					ad2.emplace_back(cr + 1, i2p->val);
				}
				lp = curl;
			}
		}
		function<void(ly*)> pmnd = [&](ly* t)
		{
			if (!t)
			{
				return;
			}
			pmnd(t->lp);
			pmnd(t->rp);
			if (t->val > cr)
			{
				ad2.emplace_back(cr + 1, t->val);
			}
		};
		pmnd(mp);
		gprt = merge(lp, rp);
		for (const auto& [x, y] : ad2)
		{
			if (x <= y)
			{
				insert(gprt, nly(x, y));
			}
		}
		const auto [pos, rem] = fbri(gprt, m);
		int res;
		if (pos != -1)
		{
			res = pos + rem * k4p;
		}
		else
		{
			int lr = 0;
			if (const ly* curr = gprt)
			{
				while (curr->rp)
				{
					curr = curr->rp;
				}
				lr = curr->val;
			}
			res = lr + 1 + rem * k4p;
		}
		cout << res << " ";
	}
	cout << endl;
}

#define CP_MULTI_TEST_CASES

signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
#ifdef CP_MULTI_TEST_CASES
	cin >> t;
#endif
	while (t--)
	{
		Main();
	}
	return cout << flush, fflush(stdout), 0;
}

信息

递交者
类型
递交
题目
P1000 云剪贴板
题目数据
下载
语言
C++
递交时间
2025-10-03 11:08:31
评测时间
2025-10-03 11:08:33
评测机
分数
0
总耗时
0ms
峰值内存
0 Bytes