Submission #341448

#	Time	Username	Problem	Language	Result	Execution time	Memory
341448		ogibogi2004	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1125 ms	111308 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll MAXN=1e6+6;
ll w[MAXN];
struct query
{
	ll r,k,pos;
};
ll ans[MAXN];
vector<query>v[MAXN];
vector<ll>g[MAXN];
ll t[MAXN],n,m;
ll fen[MAXN];
void update(ll idx,ll val)
{
	for(;idx<MAXN;idx+=idx&(-idx))
	{
		fen[idx]=max(fen[idx],val);
	}
}
ll query(ll idx)
{
	ll ret=0;
	for(;idx>0;idx-=idx&(-idx))
	{
		ret=max(ret,fen[idx]);
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(ll i=1;i<=n;++i)cin>>w[i];
	stack<pair<ll,ll> >st;
	t[1]=-1;
	st.push({w[1],1});
	for(ll i=1;i<=n;++i)
	{
		while(!st.empty()&&st.top().first<=w[i])
		{
			st.pop();
		}
		if(st.empty())
		{
			t[i]=-1;
		}
		else t[i]=st.top().second;
		st.push({w[i],i});
	}
	for(ll i=1;i<=n;++i)
	{
		if(t[i]==-1)continue;
		g[t[i]].push_back(i);
	}
	for(ll i=1;i<=m;++i)
	{
		ll l,r,k;
		cin>>l>>r>>k;
		v[l].push_back({r,k,i});
	}
	for(ll i=n;i>=1;--i)
	{
		for(ll j=0;j<g[i].size();++j)
		{
			update(g[i][j],w[i]+w[g[i][j]]);
		}
		for(ll j=0;j<v[i].size();++j)
		{
			ll t=query(v[i][j].r);
			if(t>v[i][j].k)ans[v[i][j].pos]=0;
			else ans[v[i][j].pos]=1;
		}
	}
	for(ll i=1;i<=m;++i)cout<<ans[i]<<'\n';
return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(ll j=0;j<g[i].size();++j)
      |              ~^~~~~~~~~~~~
sortbooks.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(ll j=0;j<v[i].size();++j)
      |              ~^~~~~~~~~~~~

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