oj.uz

Submission #630164

# Submission time Handle Problem Language Result Execution time Memory
630164 2022-08-15T19:16:54 Z ptrtp RMQ (NOI17_rmq) C++14
0 / 100
 5 ms 9716 KB 
#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

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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9708 KB Output is correct
3 Correct 5 ms 9712 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 5 ms 9716 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9708 KB Output is correct
3 Correct 5 ms 9712 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 5 ms 9716 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9708 KB Output is correct
3 Correct 5 ms 9712 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 5 ms 9716 KB Output isn't correct
10 Halted 0 ms 0 KB -