Submission #343659

#	Time	Username	Problem	Language	Result	Execution time	Memory
343659		Bill_00	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	3078 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 100000000000000000
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pp push
#define M 1000001
typedef long long ll;
using namespace std;

struct node{
	int ans;
	vector<int>vec;
};

node a[4*M];

int s[M];
void build(int id,int l,int r){
	if(l==r){
		a[id].ans=0;
		a[id].vec.pb(s[l]);
		return;
	}
	int m=l+r>>1;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	if(a[id*2].vec[a[id*2].vec.size()-1]<=a[id*2+1].vec[0]){
		a[id].ans=max(a[id*2].ans,a[id*2+1].ans);
	}
	else{
		int ii=(lower_bound(a[id*2+1].vec.begin(),a[id*2+1].vec.end(),a[id*2].vec[a[id*2].vec.size()-1])-a[id*2+1].vec.begin());
		a[id].ans=max(max(a[id*2].ans,a[id*2+1].ans),a[id*2].vec[a[id*2].vec.size()-1]+a[id*2+1].vec[ii-1]);
	}
	int i=0,j=0;
	while(i<a[id*2].vec.size() && j<a[id*2+1].vec.size()){
		if(a[id*2].vec[i]>a[id*2+1].vec[j]){
			a[id].vec.pb(a[id*2+1].vec[j]);
			j++;
		}
		else{
			a[id].vec.pb(a[id*2].vec[i]);
			i++;
		}
	}
	while(i<a[id*2].vec.size()){
		a[id].vec.pb(a[id*2].vec[i]);
		i++;
	}
	while(j<a[id*2+1].vec.size()){
		a[id].vec.pb(a[id*2+1].vec[j]);
		j++;
	}
}
node query(int id,int l,int r,int L,int R){
	// cout << id << '\n';
	node empty;
	if(r<L || R<l){
		return empty;
	}
	if(L<=l && r<=R){
		return a[id];
	}
	int m=l+r>>1;
	node le=query(id*2,l,m,L,R);
	node ri=query(id*2+1,m+1,r,L,R);
	if(le.vec.size()==0) return ri;
	if(ri.vec.size()==0) return le;
	if(le.vec[le.vec.size()-1]<=ri.vec[0]){
		empty.ans=max(le.ans,ri.ans);
	}
	else{
		int ii=(lower_bound(ri.vec.begin(),ri.vec.end(),le.vec[le.vec.size()-1])-ri.vec.begin());
		empty.ans=max(max(le.ans,ri.ans),le.vec[le.vec.size()-1]+ri.vec[ii-1]);
	}
	int i=0,j=0;
	while(i<le.vec.size() && j<ri.vec.size()){
		if(le.vec[i]>ri.vec[j]){
			empty.vec.pb(ri.vec[j]);
			j++;
		}
		else{
			empty.vec.pb(le.vec[i]);
			i++;
		}
	}
	while(i<le.vec.size()){
		empty.vec.pb(le.vec[i]);
		i++;
	}
	while(j<ri.vec.size()){
		empty.vec.pb(ri.vec[j]);
		j++;
	}
	return empty;
}
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> s[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int l,r,k;
		cin >> l >> r >> k;
		if(k>=query(1,1,n,l,r).ans) cout << 1 << '\n';
		else cout << 0 << '\n';
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:27:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int m=l+r>>1;
      |        ~^~
sortbooks.cpp:38:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  while(i<a[id*2].vec.size() && j<a[id*2+1].vec.size()){
      |        ~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:38:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  while(i<a[id*2].vec.size() && j<a[id*2+1].vec.size()){
      |                                ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:48:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  while(i<a[id*2].vec.size()){
      |        ~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:52:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  while(j<a[id*2+1].vec.size()){
      |        ~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'node query(int, int, int, int, int)':
sortbooks.cpp:66:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int m=l+r>>1;
      |        ~^~
sortbooks.cpp:79:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  while(i<le.vec.size() && j<ri.vec.size()){
      |        ~^~~~~~~~~~~~~~
sortbooks.cpp:79:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  while(i<le.vec.size() && j<ri.vec.size()){
      |                           ~^~~~~~~~~~~~~~
sortbooks.cpp:89:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  while(i<le.vec.size()){
      |        ~^~~~~~~~~~~~~~
sortbooks.cpp:93:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  while(j<ri.vec.size()){
      |        ~^~~~~~~~~~~~~~
sortbooks.cpp:13:8: warning: 'empty.node::ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   13 | struct node{
      |        ^~~~

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