Submission #176080

#	Time	Username	Problem	Language	Result	Execution time	Memory
176080		maskoff	Bigger segments (IZhO19_segments)	C++14	0 / 100	2 ms	380 KiB

segments

#include <bits/stdc++.h>
 
#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int inf = 1e9;
const int MOD = 1e9 + 7;

int get(int x, vector<pair<ll, pair<ll, ll>>>& all) {
 	int l = 0;
 	int r = all.size() - 1;
 	int ans = -5;
 	while (l <= r) {
 	 	int m = (l + r) / 2;
		if (all[m].sc.fr > x)
			r = m - 1;
		else        {
			ans = m;
			l = m + 1;
		}
 	}
 	return ans;
}
                                       
int main() {                                     
    ios_base::sync_with_stdio(false);
  	cin.tie(nullptr);
  	int n;
  	cin >> n;
  	vector<ll> a(n + 1);
  	vector<ll>  pref(n + 1);
  	for (int i = 1; i <= n; i++)
  		cin >> a[i];
  	for (int i = 1; i <= n; i++)
  		pref[i] = pref[i - 1] + a[i];
  	vector<pair<ll, pair<ll, ll>>> d(n + 1);
  	vector<pair<ll, pair<ll, ll>>> all;
  	for (int i = 1; i <= n; i++) {
  		int x = get(pref[i], all);
  		if (x == -5) {
  			if (all.empty() || (all.back().fr == 1 && all.back().sc.sc < pref[i])) 
  		 		all.pb({1, {2 * pref[i], pref[i]}});
  		 	continue;
  		}        
  		d[i].fr = all[x].fr + 1;         
  		d[i].sc.sc = pref[i]/* - (all[x].sc.fr - all[x].sc.sc)*/;
  		d[i].sc.fr = d[i].sc.sc + (pref[i] - all[x].sc.sc);
  		while (!all.empty() && all.back().fr < d[i].fr && all.back().sc.fr > d[i].sc.fr) 
  			all.pop_back();
  		if (all.empty())
			all.pb({d[i].fr, {d[i].sc.fr, d[i].sc.sc}});  
  		if (!all.empty() && all.back().fr >= d[i].fr)
  			continue;
  		if (!all.empty() && (all.back().fr < d[i].fr || (all.back().sc.sc > d[i].sc.sc)))
  			all.pb({d[i].fr, {d[i].sc.fr, d[i].sc.sc}});
  		  			
  	}
  	cout << all.back().fr;
    return false;
}               

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