Submission #1098324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098324		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2119 ms	141824 KiB

sortbooks

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░▒▒░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░█░▀░░░░░▌░░░░░░░░░░░░░░▄░░░░░░░░░░░░░░░░░░█░░░░░▌░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░░▌░░░░░░░▐░░░░░░░░▌░░░░██░▀▌░░░░░░░░▐▌░░░░░██░░░░▐░░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░░█▌░░░░█░░░▌░░░░░░░░█░░░░░█░▐░░░░▐░░░░░▌░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░█░▌░░░░█░░░▄░░░░░░░▐▄░███▀░░▐░░░░█░░░░██░░░░░░░░░░░░░░░░
░░░░░░░░░█░░░░░░▐█░░░░░█░▐░░░░▐▌░░░▐░░░░░░█▀░▌░░▀▌░░▐░░░░░█▄░█░░▌░░░░░░░░░░░░░░░
░░░░░░░░░░█▄░░░█░░█░░░█░░█░░░▄█▌░░░░█▄░░▄█░░░█░░░▌░░░█░▄█░░░▀░░░█▄░░░░░░░░░░░░░░
░░░░░░░░░░░░▀▀▀░░░░▀█▀░░░▌▄▄█░█░░░░░░░▀▀░░░░░░██▀░░░░░▀░░░░░░░░░░░▀▀░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░▄██▀░░░░█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▄▄█▀░█░░░░░▐█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░▌░░░░█░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░█░░▄█░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▀▀░░░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
*/
#include<bits/stdc++.h>
// #include "stress.cpp"
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie()
#define ll long long
#define ull unsigned long long
#define pb push_back
// #define endl "\n"
#define int ll
#define F first     
#define S second
#define db long double 
#define ld long double
#define short unsigned short
#define pii pair<int,int>
#define all(x) x.begin(),x.enad();
using namespace std;
const   ll inf = 1e18,MOD=1e9+7,N=1e6+10,MN=1e9+7,lim=100;
const db Pie=acos(-1);
int binpow(int a,int p);
int lcgayletiar(int a,int b);
//...and justice for all
struct surymgay{
  int l,r,k;
};
int v[N],p[N];
int t[N*4];
vector<int>q[N];
void upd(int i,int v,int x,int lx,int rx){
  if(lx==rx){
    t[x]=v;
    return ;
  }
  int m=(lx+rx)/2;
  if(i<=m){
    upd(i,v,x*2,lx,m);
  }
  else{
    upd(i,v,x*2+1,m+1,rx);
  }
  t[x]=max(t[x*2],t[x*2+1]);
}
int get(int l,int r,int x,int lx,int rx){
  if(l<=lx&&rx<=r){
    return t[x];
  }
  if(r<lx||rx<l){
    return 0;
  }
  int m=(lx+rx)/2;
  return max(get(l,r,x*2,lx,m),get(l,r,x*2+1,m+1,rx));
}
const void solve(){
  int n,m;
  cin>>n>>m;
  stack<int>s;
  for(int i=1;i<=n;i++){
    cin>>v[i];
  }
  for(int i=1;i<=n;i++){
    while(s.size()&&v[s.top()]<=v[i]){
      s.pop();
    }
    if(s.size()){
        p[i]=s.top();
    }
    s.push(i);
  }
  vector<surymgay>qu(m+1);
  for(int i=1;i<=m;i++){
    cin>>qu[i].l>>qu[i].r>>qu[i].k;
    q[qu[i].r].pb(i);
  }
  vector<int>ans(m+1);
  for(int i=1;i<=n;i++){
    if(p[i])upd(p[i],v[i]+v[p[i]],1,1,n);
    for(auto j:q[i]){
      ans[j]=get(qu[j].l,qu[j].r,1,1,n)<=qu[j].k;
    } 
  }
  for(int i=1;i<=m;i++){
    cout<<ans[i]<<endl;
  }
}
signed main() {
    srand(time(NULL));
    IOS;
    // freopen("sequence.in", "r", stdin);
    // freopen("sequence.out", "w", stdout);
    int pantyandstocking=1;
    // cin>>pantyandstocking;
    for(int i=1;i<=pantyandstocking;i++) { 
      // cout<<"Test "<<i<<": "<<endl;  
      solve(); 
      // cout<<endl;
    }
    // cout<<fixed<<setprecision(10);
    // cerr<<"Time:"<<1000*((double)clock())/(double)  CLOCKS_PER_SEC<<"ms\n"; 
}
int lcgayletiar(int a,int b){return (a*b)/(int)__gcd(a,b);}
int binpow(int a,int p){if(p==0)return 1;if(p%2){return ((binpow(a,p-1)*a)%MOD);}int res=binpow(a,p/2)%MOD; return (res*res)%MOD;}

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