Submission #1265508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265508		_rain_	RMQ (NOI17_rmq)	C++20	100 / 100	45 ms	13740 KiB

rmq

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define sz(x) (int)(x).size()
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)

template<class T1 , class T2>
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}

const int N = (int) 1e5;
const int MAXLOG = (int) 17;
	int l[N + 2] , r[N + 2] , a[N + 2] = {};
	int n , q;

namespace RMQ{
	int rmq[N + 2][MAXLOG + 2];
	int LOG[N + 2] = {};
	
	void build_rmq(){
		for(int i = 2; i <= N; ++i) LOG[i] = LOG[i / 2] + 1;
		for(int j = 1; j <= MAXLOG; ++j){
			for(int i = 1; i <= n - MASK(j) + 1; ++i){
				rmq[i][j] = min(rmq[i][j - 1] , rmq[i + MASK(j - 1)][j - 1]);
			}
		}
		return;
	}
	
	int Get_min(int l , int r){
		int x = LOG[r - l + 1];
		return min(rmq[l][x] , rmq[r - MASK(x) + 1][x]);
	}
};
using namespace RMQ;

	
namespace subtask1{
	bool check(){
		return n <= 10;
	}
	void main_code(){
		vector<int> v;
		for(int i = 0; i < n; ++i) v.push_back(i);
		do{
			for(int i = 0; i < sz(v); ++i) rmq[i + 1][0] = v[i];
			build_rmq();
			
			bool ok = true;
			for(int i = 1; i <= q && ok; ++i){
				ok &= (Get_min(l[i] , r[i]) == a[i]);
			}
			if (ok){
				for(auto& x : v) cout << x << ' '; 
				return;
			}
		} while (next_permutation(v.begin() , v.end()));
		for(int i = 1; i <= n; ++i) cout << -1 << ' ';
	}
}

namespace subtask2{
	bool check(){
		return true;
	}
	
	int id[N + 2] = {};
	int nxt[N + 2] = {} , val[N + 2] = {} , limit[N + 2] = {};
	bool used[N + 2] = {};
	
	
	int Find(int i){
		if (val[i] == -1) return i;
		return nxt[i] = Find(nxt[i + 1]);
	}
	
	void main_code(){
		for(int i = 1; i <= q; ++i) id[i] = i;
		
		sort(id + 1 , id + q + 1 , [&](int i , int j){
			if (a[i] != a[j]) return a[i] > a[j];	
			return l[i] > l[j];
		});
		
		for(int i = 1; i <= n + 1; ++i) {
			nxt[i] = i , val[i] = -1 , limit[i] = 0;
		}
		
		for(int idx = 1; idx <= q; ++idx){
			int i = id[idx];
			int t = Find(l[i]);
			for(int j = t; j <= r[i]; j = Find(j + 1)) {
				if (j == t && !used[a[i]]) val[j] = a[i]; else val[j] = -2;
				limit[j] = a[i];
				nxt[j] = r[i] + 1;
			}
			used[a[i]] = true;
		}
		set<int>s;
		for(int i = 0; i < n; ++i) if (used[i]==false) s.insert(i);
		int j = 0;
		bool ok = true;
		for(int i = 1 ; i <= n; ++i) {
			if (val[i] >= 0) continue;
			auto it = s.lower_bound(limit[i]);
			if (it == s.end()){
				ok = false;
				break;
			}
			val[i] = *it;
			s.erase(it);
		}
		for(int i = 1; i <= n; ++i) rmq[i][0] = val[i];
		build_rmq();
		for(int i = 1; i <= q && ok; ++i){
			ok &= Get_min(l[i] , r[i]) == a[i];
		}
		if (ok==false){
			for(int i = 1; i <= n; ++i) cout << -1 << ' '; 
			return;
		}
		for(int i = 1; i <= n; ++i) cout << val[i] << ' '; cout << '\n';	
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> q;
		FOR(i , 1 , q) {
			cin >> l[i] >> r[i] >> a[i];
			++l[i] , ++r[i];
		}

		if (subtask2::check()) return subtask2::main_code() , 0;
		
	return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:148:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
rmq.cpp:149:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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