# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
493187 | 2021-12-10T10:29:45 Z | irmuun | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; #define pb push_back #define ll long long #define ff first #define ss second #define PI 3.14159265359 int main(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); ll n,m,w[200001],h[200001],l,r,k,ans,i,j,b,c,mn=1e9,a,m; vector<ll>v; cin>>n>>m; for(i=1;i<=n;i++){ cin>>w[i]; if(i>1){ if(w[i]<w[i-1]){ v.pb(i); } } mn=min(mn,w[i]); h[i]=w[i]; } for(i=1;i<=m;i++){ cin>>l>>r>>k; if(k<mn){ a=0; b=v.size()-1; while(a<b){ m=(a+b)/2; if(w[m]<=l){ a=m+1; } else{ b=m; } } if(l<v[m]&&v[m]<=r){ cout<<1<<endl; } else{ cout<<0<<endl; } continue; } c=0; while(c==0){ c=1; for(j=l;j<r;j++){ if(w[j]+w[j+1]<=k&&w[j]>w[j+1]){ c=0; swap(w[j],w[j+1]); } } } c=1; for(j=l;j<r;j++){ if(w[j]>w[j+1]){ c=0; break; } } cout<<c<<endl; for(j=l;j<=r;j++){ w[j]=h[j]; } } }