제출 #1343628

#제출 시각아이디문제언어결과실행 시간메모리
1343628jellybeanStranded Far From Home (BOI22_island)C++20
0 / 100
71 ms32708 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;

const int N = 2e5+5;
int a[N], psum[N], ans[N];

struct node{
	int s,e,m,val,idx;
	node *l = nullptr, *r = nullptr;
	
	node(int S, int E){
		s=S, e=E, m=(s+e)/2;
		if(s!=e){
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	
	void upd(int x, int v){
		if(s==e) val = v, idx = x;
		else{
			if(x<=m) l->upd(x,v);
			else r->upd(x,v);
			if(l->val > r->val) val = l->val, idx = l->idx;
			else val = r->val, idx = r->idx;
		}
	}
	
	pii query(int S, int E){
		if(s==S and e==E) return {val,idx};
		else if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else{
			auto[a,b] = l->query(S,m);
			auto[c,d] = r->query(m+1,E);
			if(a > c) return {a,b};
			else return {c,d};
		}
	}
} *root;

void recurse(int l, int r, int x){
	if(l>r) return;
	int sum = psum[r]-psum[l-1];
	auto[mxval,id] = root->query(l,r);
	
	if(sum >= x){
		assert(l != r or l == 1);
		ans[id] = 1;
		recurse(l,id-1,mxval);
		recurse(id+1,r,mxval);
	}
		
	else return;
}
	
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n,m; cin>>n>>m;
	root = new node(1,n);
	for(int i=1; i<=n; i++){
		cin>>a[i];
		root->upd(i,a[i]);
		psum[i] = psum[i-1] + a[i];
	}
	
	recurse(1,n,0);
	
	for(int i=1; i<=n; i++) cout<<ans[i];
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...