#include <iostream> #include <vector> #include <random> #include <algorithm> #include <chrono> #include <queue> #define all(x) x.begin(), x.end() #define pb push_back #define fi first #define se second #define compact(v) v.erase(unique(all(v)) , v.end()) #define pi pair<int , int> #define vi vector<int> #define eb emplace_back #define FOR(i , l , r) for(int i = l; i <= r; ++ i) #define FORD(i , l , r) for(int i = l; i >= r; -- i) template <class T> bool maximize(T &a , T b){return (a < b ? a = b , true : false);} template <class T> bool minimize(T &a , T b){return (a > b ? a = b , true : false);} using namespace std; typedef long long ll; const int nd = 1e6 + 1 , mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int> dist(1 , (int)2e9); int add(int a , int b){ a += b; return (a >= mod ? a - mod : a); } int sub(int a , int b){ a -= b; return (a < 0 ? a + mod : a); } int mul(ll a , ll b){return (a * b) % mod;} int xpow(int a , int b){ if(b == 1) return a; int x = xpow(a , b / 2); if(b & 1) return mul(a , mul(x , x)); else return mul(x , x); } #include <deque> deque <pi> dq; struct event{ int l , r , w , id; bool operator<(const event &o)const{ if(r == o.r) return id < o.id; return r < o.r; } }; vector <event> E; void insert(int v , int id){ while(dq.size() && dq.back().fi <= v) dq.pop_back(); if(dq.size()){ E.pb({dq.back().se , id , v + dq.back().fi , 0}); } dq.pb({v , id}); } int bit[nd]; void up(int id , int v){ while(id) maximize(bit[id] , v) , id -= id & (-id); } int get(int id){ int res = 0; while(id < nd) maximize(res , bit[id]) , id += id & (-id); return res; } int ans[nd]; void solve(){ int n , q; cin >> n >> q; FOR(i , 1 , n){ int v; cin >> v; insert(v , i); } FOR(i , 1 , q){ int l , r , k; cin >> l >> r >> k; E.pb({l , r , k , i}); } sort(all(E)); for(auto [l , r , w , id] : E){ if(!id){ up(l , w); } else{ ans[id] = (get(l) <= w); } } FOR(i , 1 , q) cout << ans[i] << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); #define task "task" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } solve(); return 0; } /* -. ::. -: .:::::::::: ***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######: **##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%%#+########+*@%%@#*##+=@%######: #%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%%#=+###*##*+#@##@%###+=%%#####: #####***%##@%+***#%#++#######*********++***#*#+##%%%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%%#+*######*+%%###@###*=#%####: ##*****####@*+***###+=**#+==*+*###%#%%###%%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%%*#*+%%###: %##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###: *####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##: #**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%%*%+*####****@######%%**#%#: ####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%%@@%#####=%%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###. ###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%%*##*#**##**+@#######@**##: ###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##. ###*#%#%%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%%#######@+##: ###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%: ##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@ @@@=-=+##@%=##+#*#***#%###########. ##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%%=******+*****=#@@ @@@*:-#@%+=%+#*###+#@###########: :@#*#%##%#**##+#%+************#*****++***+#*+-%%@==+++*=+@=++++==@ @@#%=##%==+*++*+*****=#@@ @@@@#*#@*-@+***##+#%########%%#: #@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%%-==**#@@@@@@##%+#%%-=+++++**+**==@@ @#*+@*=##***##+*@###########: @*%%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@ @@#####@#=++**+******-@= *@@@@@@@@@@@=+#****#*+@###########: @@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@ @@######@+=+++++++*++=@ @@@@@@@@ +@@=+#****#*=%%##########: #@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@ .. @@#####%@-=***+*****=@@@@@@ .@@.@ @#=***#+#*=@@##########: @%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@ .: @@#####@@=+++++*++**=@@%@@@ -@@@:*@=*#**+#*+@*@#########: =: ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@ .. #@@#####@#=+**+*+#@@%#@##@@ @ @-=@=****+%*=@-#@%#######: : :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@ -*+ =@@#####@*=+**++#= -@% : @% -@==@=#***+@*=@% +@@######: @@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*. *:: -@@*####%#-++++##=:% @-@@% *@=-@=#***+@+=%@@. @@@%###: +@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@# @@####%%*-=+++#+=@@ : +@+=@+#**++@+=@#%@%- -##%%: ##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@ @@@*##%##===++**#@ .. :@*-@%***+*@==@###%@@%####: ###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@ ::++ =@@***#*#=-==++=@@ @#=#@*+*=#%==@@%#*###%@##. #*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@ @@@*+%##*--=+==@+ . @@+#@*=+=@#==@###%%%#####. **@ @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@ @ @@ @@@+*#+**:-==*@ . @@**@+=+*%#=+@###########. ++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@ @@ . . @@@@#=+**=--#@ +@**@+==##*-#@###########: -@@@ @#-======%%@*===*###@@@@#=----==+==-=#@@@@ @@* :@= @@@@@#*#=:#@ @*#@==+%#+*#@%##########: %@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@ ::.+@#: :#@@@@#+#@@ @#@@--%%#=#*%###########: %@@ @%@#%##++======------=========#%@@@@=====*=@#%@@%- ... @@@@@@@@# @*@#:=@#**#*@###########. @@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@ . . .*% @@@:-@##=#+#@#%#########. @@@**=@++++=:=%%##@@@##%%%##*+==@%==++******+*#@ .. . # @@*:##**##+#%##########%. +@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@= . .. =. @@@.:@*#*##+@%########### :%#**#%@=**+=%%###@@+@#%++******=*@@#=********+%@@ . @@.:@**###*+@###*%#######. :#+*##@%+**=%%###*@+##@#%*=*#***+=@%@++******+++@@ @@:.@@=#**#=@@############. ++##%@*++=#@###*%@*##@##%#=+****=#%%#=**+*****+%@ @@.=@@@=*##*=@######%###### #%%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+ . @@.#%#@%=###=#%#%####%###### :@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@ @ %@@@##@@++##=-@###%########## +-=@@=+@%####*%%%%%%###%@*##%%==+=#%#%%+=+*****==@ :=-:: @@@@*#%#@=*#+-@########=@##### **%@#*%%####*#@%@*%%#%##@#*##%@*==+%###@*=+*++*+-@@ ::: @@%%#@###%+#=.@%########+%##### #@@########*@@@@%:@%%%###@%####%@+:##@##%*=+*+++==@ :@@%%@####@**-:@%######%*#*###### @%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@ @@ =@@%######@@+ =@%################# =%#######+@@##@#+*=@##%%####@%##############@=======@ @%@-@@@#######@%: @@##########%#*###### .######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@ :. **@@:@@@#####@# +@%#############*###### .#%##+@@@%=#%@#*#**@#%%####@:=%@##%##*######*##@*=-==#@ :=@@: @ -##-@@@###%-=@%############*##+%##### :#=*@@#*=+=%%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@ :+%@@@* : @@@#*###################+%##### @@###+*#*#@%##*#+%%%@*%###@=++=%@#*#%%#*+********##*-:=@+ @@@@#: +@ *@@@#############**######*#### #####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@ @ .-+#%@@@@@@@@@@@@@@ #@@@%#############*#*#####** ####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@% @@ :::::::. #@ @@%###@@ @@@@#########**##******** .#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@ @%:.::::::--:: @@ =@*#=#*@@@@ +@@@#*#*******###*###** #####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#* @@@@#@@+=+****@@@+ : @@ +@#=:%#@ @@@% @@@%#######**#**+*** .####**%%**###**%@@ @%#@@ #%#=##==#*@@ @@@@@ @@@@@@@+==+*#@@@@@=: :#@@@ @@ =@#=-###@ #@@@@ @@@@#************* ####*#%*#####+#@@ =@%%@ @+@#=+#==#*@* . +@@@@ *@@@*=++==#@@@@@@@: @@:-@#=-*##@= @@#@@@ #@@@#*********** .#######**###**@@= @@@@+ ##@#=+#*=##@ ::. :@@@@@@@- :@*@@@@@@= : -@@=#+==+##*@@: %==@@@@ @@@@#****++++ ######*##*##*@@# *@@@= @#@@#=++@+##@ +#= @@@@#+-*%@@@@@@@@@%. %@@@@@@%= @=@#+===##++=%@:@=:#@@@@ -@@@@%#**** #####**##*+*#@% =@%@@.*@@ @%+++=#*@@ . @@@==@@@@@@- .@@@@@+===*+@=## @@@#-+%*@@@: =@@@*++ ####***#*+*#@@ :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@# @@@+====@.#@= @@%==#**@@@- :=:::. @@*+ ##*+*##*++@@@ #@#@@@ @#@ @@#++=*%@ *@%%@@@ . @@#===#=:@@@ @@@%@@@@@@@@= .-: #@* .##**#****%@@. @@*@@= .@#@ @@@+=++@ @@%@@@ ......:: #@@===@ @@@@ ::#@@= . .:-. @@ #+***++#%@@ @##@@ %@#@ *: @@@+=*@@@@@@ .... . ..::. @@+-*@ @@@. ... . # *#****##%% +@*#@% .: @@#@ :@@@#@@@@ ... .. .:. @@#=#@ - ....... **++##### @##@@: ::: =@#@ .: @@@ ......... . .. .. @%#*@: # : .=**=:.. ..:. ++*####**#**@@ :::: @@@@ @@@: .:.......... ... . . .: -@#+#@ : .:::..:=#%@@@@= ......... +######*+*@@* ::::::: @@@@@@@@ ..:....... ..... . ... . . %+**%@ .. # -** . . ..:... ##**#*+=#@@: ::::::::. . :...:........... . .. .. ##-=#@ . =@@= . ...... ####*+#@@* :::-::::: ==-=: .::.:::.. ... .. .... ... ##=-=@ :#+. .::. ...:::: */

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~