Submission #630164

#	Time	Username	Problem	Language	Result	Execution time	Memory
630164		ptrtp	RMQ (NOI17_rmq)	C++14	0 / 100	5 ms	9716 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 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++) {
		printf("%d ", sol[i]);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

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

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