Submission #699620

#	Time	Username	Problem	Language	Result	Execution time	Memory
699620		anonimy	RMQ (NOI17_rmq)	C++14	100 / 100	58 ms	12620 KiB

rmq

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

struct seg
{
	vector<ll> a;
	ll sz;
	
	seg(ll n)
	{
		for (sz = 1; sz < n; sz <<= 1);
		a.resize(sz * 2, 0);
	}

	void update(ll l, ll r, ll x)
	{
		l += sz, r += sz;

		while (l<=r)
		{
			if (l % 2 == 1) a[l] = max(a[l], x), l++;
			if (r % 2 == 0) a[r] = max(a[r], x), r--;
			l >>= 1;
			r >>= 1;
		}
	}

	ll q(ll ind)
	{
		ind += sz;
		ll ans = a[ind];
		for (ind >>= 1; ind; ind >>= 1)
			ans = max(ans, a[ind]);
		return ans;
	}
};

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n, q;
	cin >> n >> q;

	vector<pll> range(n, {0, n - 1});
	seg s(n);
	while (q--)
	{
		ll l, r, a;
		cin >> l >> r >> a;

		s.update(l, r, a);
		range[a].first = max(range[a].first, l);
		range[a].second = min(range[a].second, r);
	}

	vector<vector<ll>> indexs(n);
	for (ll i = 0; i < n; i++)
	{
		ll maxx = s.q(i);
		indexs[maxx].push_back(i);
	}

	set<ll> op;
	vector<ll> ans(n);
	for (ll i = 0; i < n; i++)
	{
		for (ll j = 0; j < indexs[i].size(); j++)
			op.insert(indexs[i][j]);
		
		auto it = op.lower_bound(range[i].first);
		if (it == op.end() || (*it) > range[i].second)
		{
			for (ll k = 0; k < n; k++)
				cout << -1 << " ";
			return 0;
		}

		ans[(*it)] = i;
		op.erase(it);
	}

	for (ll i = 0; i < n; i++)
		cout << ans[i] << " ";

	return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:75:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (ll j = 0; j < indexs[i].size(); j++)
      |                  ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33