oj.uz

Submission #959866

# Submission time Handle Problem Language Result Execution time Memory
959866 2024-04-09T08:53:06 Z pcc Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1302 ms 151284 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e6+10;

struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
	pll seg[mxn*4];
	SEG(){
		for(auto &i:seg)i.fs = i.sc = 0;
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&e>=r){
			seg[now].sc += v;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		seg[now].fs = max(seg[ls].fs+seg[ls].sc,seg[rs].fs+seg[rs].sc);
		return;
	}
	ll getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now].fs+seg[now].sc;
		if(mid>=e)return getval(ls,l,mid,s,e)+seg[now].sc;
		else if(mid<s)return getval(rs,mid+1,r,s,e)+seg[now].sc;
		else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e))+seg[now].sc;
	}
};

SEG seg;
vector<int> st;
int arr[mxn];
vector<pii> ask[mxn];
int N,Q;
int need[mxn],ans[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	for(int i = 1;i<=Q;i++){
		int l,r;
		cin>>r>>l;
		cin>>need[i];
		l = N+1-l,r = N+1-r;
		ask[r].push_back(pii(l,i));
	}
	reverse(arr+1,arr+N+1);
	arr[0] = 1e9+10;
	for(int i = 1;i<=N;i++){
		seg.modify(0,1,N,i,i,arr[i]);
	}
	st.push_back(0);
	for(int i = 1;i<=N;i++){
		while(arr[st.back()]<arr[i]){
			if(st.end()[-2]+1 != st.back())seg.modify(0,1,N,st.end()[-2]+1,st.end()[-1]-1,-arr[st.back()]);
			st.pop_back();
		}
		if(st.back()+1 != i)seg.modify(0,1,N,st.back()+1,i-1,arr[i]);
		st.push_back(i);
		for(auto &j:ask[i])ans[j.sc] = seg.getval(0,1,N,j.fs,i);
	}
	for(int i = 1;i<=Q;i++)cout<<(ans[i]<=need[i])<<'\n';
	return 0;
}

Compilation message

sortbooks.cpp: In member function 'void SEG::modify(int, int, int, int, int, int)':
sortbooks.cpp:23:7: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   23 |   if(l>=s&e>=r){
      |      ~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 88148 KB Output is correct
2 Correct 23 ms 88144 KB Output is correct
3 Incorrect 20 ms 88152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 88148 KB Output is correct
2 Correct 23 ms 88144 KB Output is correct
3 Incorrect 20 ms 88152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 88148 KB Output is correct
2 Correct 23 ms 88144 KB Output is correct
3 Incorrect 20 ms 88152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 88148 KB Output is correct
2 Correct 23 ms 88144 KB Output is correct
3 Incorrect 20 ms 88152 KB Output isn't correct
4 Halted 0 ms 0 KB -