Submission #630167

#	Time	Username	Problem	Language	Result	Execution time	Memory
630167		ptrtp	RMQ (NOI17_rmq)	C++14	100 / 100	122 ms	20972 KiB

rmq

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, q;
int l[maxn], r[maxn], val[maxn];
int mini[maxn], maxi[maxn];
multiset< int > s;
vector< int > events[maxn];
vector< int > pos[maxn];
int sol[maxn];
int tour[treesiz];

int query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return inf;
	if (l >= a && r <= b) return tour[node];

	int mid = (l + r) / 2;
	return min(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++) maxi[i] = n - 1;
	for (int i = 1; i <= q; i++) {
		scanf("%d%d%d", l+i, r+i, val+i);
		mini[val[i]] = max(mini[val[i]], l[i]);
		maxi[val[i]] = max(maxi[val[i]], r[i]);

		events[l[i]].push_back(i);
		events[r[i] + 1].push_back(-i);
	}

	s.insert(0);
	for (int i = 0; i < n; i++) {
		for (int tren : events[i]) {
			if (tren > 0) s.insert(val[tren]);
			else s.erase(s.find(val[-tren]));
		}
		pos[*s.rbegin()].push_back(i);
	}

	s.clear();
	for (int i = 0; i < n; i++) {
		for (int tren : pos[i]) s.insert(tren);
		auto iter = s.lower_bound(mini[i]);

		if (iter == s.end() || *iter > maxi[i]) {
			for (int j = 0; j < n; j++) 
				printf("-1 ");
			printf("\n");
			return 0;
		} else {
			sol[*iter] = i;
			s.erase(iter); 
		}
	}

	for (int i = 0; i < n; i++) tour[i + off] = sol[i];
	for (int i = off - 1; i > 0; i--) tour[i] = min(tour[i * 2], tour[i * 2 + 1]);

	for (int i = 1; i <= q; i++) {
		if (query(l[i], r[i], 0, off - 1, 1) != val[i]) {
			for (int j = 0; j < n; j++) 
				printf("-1 ");
			printf("\n");
			return 0;
		}
	}

	for (int i = 0; i < n; i++) {
		printf("%d ", sol[i]);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
rmq.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d%d%d", l+i, r+i, val+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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