제출 #959869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959869		pcc	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1464 ms	180144 KiB

sortbooks

#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>
#define int 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];

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;
}

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In member function 'void SEG::modify(long long int, long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:23:7: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   23 |   if(l>=s&e>=r){
      |      ~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main(){
      | ^~~~

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