oj.uz

Submission #1091897

# Submission time Handle Problem Language Result Execution time Memory
1091897 2024-09-22T13:47:34 Z ihne Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1086 ms 137252 KB 
#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,i,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

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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55124 KB Output is correct
2 Correct 22 ms 55132 KB Output is correct
3 Incorrect 22 ms 55132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55124 KB Output is correct
2 Correct 22 ms 55132 KB Output is correct
3 Incorrect 22 ms 55132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1086 ms 137252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 62056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55124 KB Output is correct
2 Correct 22 ms 55132 KB Output is correct
3 Incorrect 22 ms 55132 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 55124 KB Output is correct
2 Correct 22 ms 55132 KB Output is correct
3 Incorrect 22 ms 55132 KB Output isn't correct
4 Halted 0 ms 0 KB -