Submission #889302

#	Time	Username	Problem	Language	Result	Execution time	Memory
889302		kim	Bigger segments (IZhO19_segments)	C++17	100 / 100	130 ms	32880 KiB

segments

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define eb emplace_back

ll a[500005],qs[500005];
struct A{
	int cnt;
	ll val;
	A(int cnt_=0,ll val_=0):cnt(cnt_),val(val_){}
	bool operator<(const A&o)const{
		if(cnt!=o.cnt) return cnt>o.cnt;
		return val<o.val;
	}
	friend A operator+(A l,A r){
		l.cnt+=r.cnt;
		l.val+=r.val;
		return l;
	}
}dp[500005];
struct fenwick{
	vector<A> bit;
	void init(int n){bit=vector<A>(n);}
	void upd(int i,A x){for(;i<bit.size();i+=i&-i) bit[i]=min(bit[i],x);}
	A qr(int i){
		A x(0,0);
		for(;i>0;i-=i&-i) x=min(x,bit[i]);
		return x;
	}
}fw;

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int n; cin>>n;
	vector<ll> comp;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		qs[i]=qs[i-1]+a[i];
		comp.eb(qs[i]);
	}
	comp.erase(unique(comp.begin(),comp.end()),comp.end());
	fw.init(comp.size()+5);
	for(int i=1;i<=n;++i){
		dp[i]=fw.qr(lower_bound(comp.begin(),comp.end(),qs[i])-comp.begin()+1)+A(1,qs[i]);
		fw.upd(lower_bound(comp.begin(),comp.end(),qs[i]+dp[i].val)-comp.begin()+1,A(dp[i].cnt,-qs[i]));
	}
	cout<<dp[n].cnt;

	return 0;
}

Compilation message (stderr)

segments.cpp: In member function 'void fenwick::upd(int, A)':
segments.cpp:24:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  void upd(int i,A x){for(;i<bit.size();i+=i&-i) bit[i]=min(bit[i],x);}
      |                           ~^~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27