Submission #336061

#	Time	Username	Problem	Language	Result	Execution time	Memory
336061		tengiz05	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1410 ms	93036 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 1e6+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N], n, k, sz=1;
pii Q[N];
vector<int> L[N];
int t[N*2];
void update(int p, int val){
	p+=n;
	for(t[p]=max(val,t[p]);p>1;p>>=1)t[p>>1]=max(t[p], t[p^1]);
}
int get(int l, int r){
	int res = 0;
	for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
		if(l%2==1)res=max(t[l++],res);
		if(r%2==0)res=max(t[r--],res);
	}return res;
}
void solve(int test_case){
	int i, j, q;
	cin >> n >> q;
	while(sz<n)sz<<=1;sz=n;
	for(i=0;i<n;i++){
		cin >> a[i];
	}
	vector<int> ans(q);
	for(i=0;i<q;i++){
		int l, r, k;
		cin >> l >> r >> k;
		l--,r--;
		L[r].pb(i);
		Q[i] = {l, k};
	}
	vector<pii> v;
	
	for(i=0;i<n;i++){
		while(v.size() && v.back().ff < a[i])v.pop_back();
		bool f=0;
		if(!v.size()){
			v.pb({a[i], i});
			f=1;
		}
		if(v.back().ff > a[i])update(v.back().ss, v.back().ff+a[i]);
		if(!f)v.pb({a[i],i});
		for(auto idx : L[i]){
			ans[idx] = (get(Q[idx].ff, i) <= Q[idx].ss);
		}
		v.pb({a[i], i});
	}
	for(i=0;i<q;i++)cout << ans[i] << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void solve(long long int)':
sortbooks.cpp:32:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   32 |  while(sz<n)sz<<=1;sz=n;
      |  ^~~~~
sortbooks.cpp:32:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   32 |  while(sz<n)sz<<=1;sz=n;
      |                    ^~
sortbooks.cpp:30:9: warning: unused variable 'j' [-Wunused-variable]
   30 |  int i, j, q;
      |         ^

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