Submission #646217

#	Time	Username	Problem	Language	Result	Execution time	Memory
646217		ymm	Bigger segments (IZhO19_segments)	C++17	100 / 100	62 ms	17076 KiB

segments

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 500'010;
vector<int> vec;
ll sum[N];
ll lst[N];
int len[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, p = 0;
	ll csum = 0;
	cin >> n;
	vec.push_back(0);
	Loop (i,0,n) {
		int x;
		cin >> x;
		csum += x;
		if (p > vec.size())
			p = vec.size()-1;
		while (p+1 < vec.size() && csum >=   sum[vec[p+1]]
		                                   + lst[vec[p+1]])
			++p;
		len[i+1] = len[vec[p]]+1;
		lst[i+1] = csum - sum[vec[p]];
		sum[i+1] = csum;
		ll val = lst[i+1] + csum;
		while (val <= sum[vec.back()] + lst[vec.back()])
			vec.pop_back();
		vec.push_back(i+1);
	}
	cout << len[n] << '\n';
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:26:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   if (p > vec.size())
      |       ~~^~~~~~~~~~~~
segments.cpp:28:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while (p+1 < vec.size() && csum >=   sum[vec[p+1]]
      |          ~~~~^~~~~~~~~~~~

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