Submission #376944

#	Time	Username	Problem	Language	Result	Execution time	Memory
376944		jamezzz	Bigger segments (IZhO19_segments)	C++14	100 / 100	97 ms	16108 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, int> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

int n,a[500005],ans[500005];
ll pfx[500005],sz[500005];
deque<int> dq;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		pfx[i]=pfx[i-1]+a[i];
	}
	dq.push_back(0);
	for(int i=1;i<=n;++i){
		while(dq.size()>=2&&sz[dq[1]]<=pfx[i])dq.pop_front();
		int l=dq.front();
		debug("%d\n",l);
		ans[i]=ans[l]+1;
		sz[i]=2*pfx[i]-pfx[l];
		while(sz(dq)&&sz[dq.back()]>=sz[i])dq.pop_back();
		dq.push_back(i);
	}
	printf("%d\n",ans[n]);
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
segments.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~

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