Submission #340488

#	Time	Username	Problem	Language	Result	Execution time	Memory
340488		katearima	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3085 ms	20292 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,m, a[N], tree[2*N+1], mxswap[2*N+1], ans, high;
struct books {
	int x, y;
	int sum;
};
stack<int> st;
vector<books> v;
void update (int i, int x, int y, int l, int r, int k){
    if(l>=x && r<=y) {

        tree[i]=max(tree[i], k);
        //cout<<x<<" "<<y<<tree[i]<<endl;
        int mid=(x+y)/2;
        update(2*i+1, x, mid , l , r, k);
        update(2*i+2, mid+1, y, l, r, k);
    }
    else return;
}
int getmax(int i, int x, int y, int l , int r){
    //cout<<x<<" "<<y<<" "<<tree[i]<<endl;
	if(y<l || x>r) return 0;
	if(x>=l && y<=r){
		return tree[i];
	}
	int mid=(x+y)/2;
	return max(getmax(2*i+1, x, mid, l , r), getmax(2*i+2, mid+1, y, l ,r ));

}
main(){
	cin>>n>>m;
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
    for(int i=n-1; i>=0; i--){

		while(st.size()!=0 && a[st.top()]<a[i]){
			v.push_back({i, st.top(), a[i]+a[st.top()] });
			st.pop();
		}
        if(st.size()==0 || a[i]<a[st.top()]){
    		st.push(i);
		}
	}
	for(int i=0; i<v.size(); i++){
        //cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].sum<<endl;
        update(0,0,n-1,v[i].x, v[i].y, v[i].sum);
	}
	int d=v.size(); int mx=0;
	for(int i=0; i<m; i++){
		mx=0;
        int l , r,k;
        cin>>l>>r>>k;
        l--; r--;
        
        for(int j=0; j<d; j++){
        	if(l<=v[j].x && r>=v[j].y) mx=max(mx, v[j].sum);

		}        	
		if(k>=mx) cout<<"1"<<endl;
        else cout<<"0"<<endl;
        	
        //cout<<getmax(0,0,n-1,l, r)<<endl;
        //if(k>=getmax(0,0,n-1,l, r)) cout<<"1"<<endl;
        //else cout<<"0"<<endl;
	}


}

Compilation message (stderr)

sortbooks.cpp:32:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      |      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<books>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0; i<v.size(); i++){
      |               ~^~~~~~~~~

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