Submission #898116

#	Time	Username	Problem	Language	Result	Execution time	Memory
898116		Litusiano	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	21 / 100	3015 ms	216380 KiB

sortbooks

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

#define endl '\n'

struct MST{
	int n;
	vector<vector<int>> seg;
	void init(int n1){
		n = 1;
		while(n < n1) n*=2;
		seg.assign(2*n, vector<int>());
	}
 
	void merge(int i, int j, int k){
		int l = 0;
		int r = 0;
		while(l < seg[j].size() && r < seg[k].size()){
			if(seg[j][l] < seg[k][r]){
				seg[i].push_back(seg[j][l]); l++;
			}
			else{
				seg[i].push_back(seg[k][r]); r++;
			}
		}
		while(l < seg[j].size()){
			seg[i].push_back(seg[j][l]); l++;
		}
		while(r < seg[k].size()){
			seg[i].push_back(seg[k][r]); r++;
		}
	}
 
	void build(vector<int> v){
		for(int i = n; i < 2*n; i++){
			if(i-n >= v.size()) seg[i].push_back(0);
			else seg[i].push_back(v[i-n]);
		}
		for(int i = n-1; i>=0; i--){
			merge(i,2*i, 2*i+1);
		}
	}
 
	int query(int ql, int qr, int v, int k, int l, int r){
		if(r < ql || l > qr) return 0;
		if(ql <= l && r<= qr){
			auto it = lower_bound(seg[k].begin(),seg[k].end(), v);
			if(it == seg[k].begin()) return 0;
			return *(it-1);
		}
		int m = (l+r) / 2;
		int x = query(ql, qr, v, 2*k, l ,m);
		int y = query(ql, qr, v, 2*k+1, m+1 ,r);
		return max(x,y);
	}
 
	int query(int ql, int qr, int v){
		return query(ql, qr, v, 1, 0, n-1);
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
  int n,q; cin>>n>>q;
  vector<int> v(n); for(int& i : v) cin>>i;
  vector<int> pre(n+1);
 	for(int i = 1; i<n; i++){
  	pre[i+1] = pre[i] + (v[i] < v[i-1]); 
  }
  MST seg; seg.init(n); seg.build(v);
  while(q--){
  	int l,r,k; cin>>l>>r>>k;
  	if(n > 6000){
  		if(pre[r] - pre[l] == 0) cout<<1<<endl;
  		else cout<<0<<endl;
  	}
  	else{
  		l--; r--;
  		int mx = 0;
	  	for(int i = l; i < r; i++){
	  		// cerr<<i+1<<" "<<r<<endl;
	  		// cerr<<"QUERY: "<<i<<" "<< seg.query(i+1,r,v[i])<<endl;
	  		int x = seg.query(i+1,r,v[i]);
	  		if(!x) continue;
	  		mx = max(mx, v[i] + x);
	  	}
	  	if(mx > k) cout<<0<<endl;
	  	else cout<<1<<endl;
  	}
  	
  	
  }
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void MST::merge(int, int, int)':
sortbooks.cpp:18:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   while(l < seg[j].size() && r < seg[k].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp:18:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   while(l < seg[j].size() && r < seg[k].size()){
      |                              ~~^~~~~~~~~~~~~~~
sortbooks.cpp:26:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   while(l < seg[j].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp:29:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   while(r < seg[k].size()){
      |         ~~^~~~~~~~~~~~~~~
sortbooks.cpp: In member function 'void MST::build(std::vector<int>)':
sortbooks.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    if(i-n >= v.size()) seg[i].push_back(0);
      |       ~~~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23