Submission #343676

#	Time	Username	Problem	Language	Result	Execution time	Memory
343676		Bill_00	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	2230 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=-1e9;
		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++;
	}
}
int query1(int id,int l,int r,int L,int R){
	if(r<L || R<l){
		return -1e9;
	}
	if(L<=l && r<=R){
		return a[id].vec[a[id].vec.size()-1];
	}
	int m=l+r>>1;
	return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
int query2(int id,int l,int r,int L,int R,int k){
	if(r<L || R<l){
		return -1e9;
	}
	if(L<=l && r<=R){
		if(a[id].vec[0]>=k) return -1e9;
		else{
			int ii=(lower_bound(a[id].vec.begin(),a[id].vec.end(),k)-a[id].vec.begin());
			return a[id].vec[ii-1];
		}
	}
	int m=l+r>>1;
	return max(query2(id*2,l,m,L,R,k),query2(id*2+1,m+1,r,L,R,k));
}
int query(int id,int l,int r,int L,int R){
	// cout << id << '\n';
	if(r<L || R<l){
		return -1e9;
	}
	if(L<=l && r<=R){
		return a[id].ans;
	}
	int m=l+r>>1;
	int b=query1(id*2,l,m,L,R);
	int c=query2(id*2+1,m+1,r,L,R,b);
	// cout << id << ' ' << b << ' ' << c << '\n';
	return max(max(query(id*2,l,m,L,R),query(id*2+1,m+1,r,L,R)),b+c);
	
}
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)) 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 'int query1(int, int, int, int, int)':
sortbooks.cpp:64:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int m=l+r>>1;
      |        ~^~
sortbooks.cpp: In function 'int query2(int, int, int, int, int, int)':
sortbooks.cpp:78:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int m=l+r>>1;
      |        ~^~
sortbooks.cpp: In function 'int query(int, int, int, int, int)':
sortbooks.cpp:89:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |  int m=l+r>>1;
      |        ~^~

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