Submission #1091899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091899		ihne	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1097 ms	139932 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
const int mn=1e6+5;
const int mod=1e9+7;
int st[4*mn];
int a[mn];
struct query{
	int l,k,id;
};
vector<query> q[mn];
void update(int id,int l,int r,int pos,int val){
	if (l>pos||r<pos) return;
	if (l==r){
		st[id]=val;
		return;
	}
	int mid=l+r>>1;
	update(id<<1,l,mid,pos,val);
	update(id<<1|1,mid+1,r,pos,val);
	st[id]=max(st[id<<1],st[id<<1|1]);
}
int get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return -1e9;
	if (l>=u&&r<=v) return st[id];
	int mid=l+r>>1;
	return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
int ans[mn];
signed main(){
  //freopen("","r",stdin);
  //freopen("","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,m;
  cin>>n>>m;
  for (int i=1;i<=n;i++){
  	cin>>a[i];
	}
	memset(st,-0x3f,sizeof(st));
	for (int i=1;i<=m;i++){
		int l,r,k;
		cin>>l>>r>>k;
		q[r].pb({l,k,i});
	}
	stack<pii> s;
	for (int i=1;i<=n;i++){
		while (!s.empty()&&s.top().fi<a[i]) s.pop();
		if (!s.empty()&&a[i]!=s.top().fi) update(1,1,n,s.top().se,a[i]+s.top().fi);
		s.push({a[i],i});
		for (query x:q[i]) ans[x.id]=(get(1,1,n,x.l,i)<=x.k);
	}
	for (int i=1;i<=m;i++) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

sortbooks.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:22:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |  int mid=l+r>>1;
      |          ~^~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int mid=l+r>>1;
      |          ~^~

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