oj.uz

Submission #959867

# Submission time Handle Problem Language Result Execution time Memory
959867 2024-04-09T08:58:00 Z pcc Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 1279 ms 120132 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;
	}
};

const ll inf = 2e9+10;
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));
	}
	seg.modify(0,1,N,0,N,-inf);
	reverse(arr+1,arr+N+1);
	arr[0] = 1e9+10;
	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()]);
			seg.modify(0,1,N,st.back(),st.back(),inf+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:22:7: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   22 |   if(l>=s&e>=r){
      |      ~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 91732 KB Output is correct
2 Correct 19 ms 91896 KB Output is correct
3 Incorrect 21 ms 91736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 91732 KB Output is correct
2 Correct 19 ms 91896 KB Output is correct
3 Incorrect 21 ms 91736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 98388 KB Output is correct
2 Correct 92 ms 99716 KB Output is correct
3 Correct 78 ms 100808 KB Output is correct
4 Correct 80 ms 100992 KB Output is correct
5 Correct 79 ms 101076 KB Output is correct
6 Correct 64 ms 99708 KB Output is correct
7 Correct 64 ms 99792 KB Output is correct
8 Correct 75 ms 99896 KB Output is correct
9 Correct 50 ms 98788 KB Output is correct
10 Correct 74 ms 100044 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 91732 KB Output is correct
2 Correct 19 ms 91896 KB Output is correct
3 Incorrect 21 ms 91736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 91732 KB Output is correct
2 Correct 19 ms 91896 KB Output is correct
3 Incorrect 21 ms 91736 KB Output isn't correct
4 Halted 0 ms 0 KB -