Submission #339081

#	Time	Username	Problem	Language	Result	Execution time	Memory
339081		Khizri	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	3073 ms	33388 KiB

sortbooks

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
//------------------------------------------------------------------------------
//******************************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define ll long long
#define MOD 1e9+7
#define endl '\n'
const int mxn=1e6+5;
//******************************************************************************
//------------------------------------------------------------------------------
ll t=1,n,m,arr[mxn],l,r,k;
vector<ll>vt[1010];
bool binary_search(ll ind,ll a,ll b){
	ll l=0,r=vt[ind].size()-1;
	while(l<=r){
		ll m=(l+r)/2;
		if(vt[ind][m]>b){
			r=m-1;
		}
		else if(vt[ind][m]<a){
			l=m+1;
		}
		else{
			//cout<<m<<endl;
			return true;
		}
	}
	return false;
}
bool funk(){
	multiset<ll>st;
	for(int i=l;i<=r;i++){
		st.insert(arr[i]);
	}
	for(int i=l;i<=r;i++){
		st.erase(st.find(arr[i]));
		multiset<ll>::iterator it=st.lower_bound(arr[i]);
		if(it!=st.begin()){
			it--;
			if((*it)+arr[i]>k){
				return false;
			}
		}
	}
	return true;
}
bool f(){
	for(ll i=l;i<r;i++){
		for(int j=arr[i]-1;j>max(-1ll,k-arr[i]);j--){
			if(binary_search(j,i+1,r)){
				return false;
			}
		}
	}
	return true;
}
void solve(){
	bool x=true;
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&arr[i]);
		if(arr[i]>1000) x=false;
		if(x) vt[arr[i]].pb(i);
	}
	while(m--){
		scanf("%lld %lld %lld",&l,&r,&k);
		int q;
		if(x){
			q=f();
		}
		else{
			q=funk();
		}
		printf("%d\n",q);
	}
	
}
int main(){
	//IOS;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  scanf("%lld %lld",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf("%lld",&arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |   scanf("%lld %lld %lld",&l,&r,&k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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