Submission #757252

#	Time	Username	Problem	Language	Result	Execution time	Memory
757252		Doncho_Bonboncho	RMQ (NOI17_rmq)	C++14	100 / 100	88 ms	35276 KiB

rmq

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

#ifndef LOCAL
#define cerr if(false) cerr
#endif

std::vector<std::pair<int, int>>  Q[MAX_N];
std::set<int> pos;
std::set<int> nums;
bool use[MAX_N];
int nas[MAX_N];
int main () {

#ifndef LOCAL
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
#endif

	int n, q;
	std::cin>>n>>q;
	for( int i=0 ; i<q ; i++ ){
		int a, b, c;
		std::cin>>a>>b>>c;
		Q[c].push_back({a, b});
	}
	for( int i=0 ; i<n ; i++ ){
		pos.insert(i);
		nums.insert(i);
	}


	bool oke = true;
	for( int i=n-1 ; i>=0 ; i-- ){
		if( Q[i].size() == 0 ) continue;
		int smMin = 0, smMax = n-1;
		int bgMin = n-1, bgMax =0;
		for( auto j : Q[i] ){
			smMin = std::max( smMin, j.first );
			smMax = std::min( smMax, j.second );
			bgMin = std::min( bgMin, j.first );
			bgMax = std::max( bgMax, j.second );
		}
		//std::cerr<<smMin<<" "<< smMax<<" , "<<bgMin<<" "<<bgMax<<"\n";
		if( smMax < smMin ){
			oke = false;
			break;
		}
		auto it = pos.lower_bound( smMin );
		if( it == pos.end() || *it > smMax ){
			oke = false;
			break;
		}
		if( nums.find(i) == nums.end() ){
			oke = false;
			break;
		}
		//std::cerr<<" ! "<<i<<"\n";
		nas[*it] = i;
		use[*it] = true;
		//if( nums.find( i ) == nums.end() ) std::cerr<<" chep \n";
		//std::cerr<<" erase :"<<i<<"\n";
		nums.erase( i );
		pos.erase( it );
		while( true ){
			auto curr = pos.lower_bound( bgMin );
			if( curr == pos.end() || *curr > bgMax ) break;
			//std::cerr<<*curr<<" , ";
			if( *nums.rbegin() < i ){
				oke = false;
				break;
			}
			use[*curr] = true;
			pos.erase( curr );
			nas[*curr] = *nums.rbegin();
			nums.erase( *nums.rbegin() );
		}
		if( !oke ) break;

	}

	if( !oke ){
		for( int i=0 ; i<n ; i++ ) std::cout<<"-1 ";
		std::cout<<"\n";
		return 0;
	}

	for( int i=0 ; i<n ; i++ ){
		if( !use[i] ){
			nas[i] = *nums.rbegin();
			nums.erase( *nums.rbegin() );
		}
	}
	for( int i = 0; i<n ; i++ ) std::cout<<nas[i]<<" ";
	std::cout<<"\n";

	return 0;
}
// i dont know, where i'm going, but i hope that i'm on the right path

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