oj.uz

Submission #537384

# Submission time Handle Problem Language Result Execution time Memory
537384 2022-03-15T04:13:55 Z ac2hu RMQ (NOI17_rmq) C++14
67 / 100
 1000 ms 10124 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
const int N = 1e5 + 10;
int n,m;
int ans[N], uq[N];
pair<int,int> seq[N];
pair<int,int> fseq[N];
signed main() {
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin >> n >> m;
	for(int i =0 ;i<n;i++){
		ans[i] = -1;
		seq[i] = {-1,-1};
		fseq[i] = {-1,-1};
	}
	auto merge = [&](pair<int,int> a,pair<int,int> b) -> pair<int,int>{
		return {min(a.first,b.first), max(a.second,b.second)};
		// LARGEST RANGE WHERE IT IS MINIMUM
	};
	for(int _ = 0;_<m;_++){
		int l,r,a;cin >> l >> r >> a;
		if(seq[a].first == -1){
			seq[a] = {l,r};
			fseq[a] = {l,r};
		}
		else{
			fseq[a] = {max(fseq[a].first,l), min(fseq[a].second,r)};
			seq[a] = merge(seq[a], {l,r});
		}
	}
	for(int i = 0;i<n;i++){
		if(seq[i].second < seq[i].first){
				for(int i= 0;i<n;i++){
					cout << -1 << " ";
				}
				exit(0);
			}
		}
		// deb(i,seq[i]);
	set<int> s;
	for(int i = 0;i<n;i++)
		s.insert(i);
	vector<int> not_selected;
	for(int i = n - 1;i>=0;i--){
		if(seq[i].first == -1)
			not_selected.push_back(i);
		else{
			auto temp = s.lower_bound(fseq[i].first);
			if(temp == s.end() || *temp > fseq[i].second){
				for(int i= 0;i<n;i++){
					cout << -1 << " ";
				}
				exit(0);
			}
			else{
				uq[*temp] = i;
				ans[*temp] = i;
				s.erase(temp);
			}
			set<int> temp1 = s;
			auto it = s.lower_bound(seq[i].first);
			// --it;
			auto end = s.upper_bound(seq[i].second);
			for(auto tt = it;tt != end;++tt){
				uq[*tt] = max(i, uq[*tt]);
				temp1.erase(temp1.find(*tt));
			}
			swap(temp1,s);
		}
	}
	// for(int i =0;i<n;i++)
		// cout << ans[i] << " ";
	// cout << "\n";
	vector<int> temp;
	for(int i =0;i<n;i++){
		if(ans[i] == -1)
			temp.push_back(i);
	}
	sort(temp.begin(),temp.end(),[&](int a,int b){
		return uq[a] < uq[b];
	});
	deb(temp);
	// cout << temp.back() << "\n";
	for(int i = n - 1;i>=0;i--){
		if(seq[i].first == -1){
			if(uq[temp.back()] > i){
				for(int i= 0;i<n;i++)
					cout << -1 << " ";
				exit(0);
			}
			ans[temp.back()] = i;
			temp.pop_back();
		}
	}
	for(int i =0 ;i<n;i++)
		cout << ans[i] << " ";
	cout << "\n";
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #2
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 328 KB Output is correct
23 Correct 1 ms 456 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 328 KB Output is correct
23 Correct 1 ms 456 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Execution timed out 1065 ms 10124 KB Time limit exceeded
28 Halted 0 ms 0 KB -