oj.uz

Submission #176075

# Submission time Handle Problem Language Result Execution time Memory
176075 2020-01-07T20:25:49 Z maskoff Bigger segments (IZhO19_segments) C++14
0 / 100
 2 ms 376 KB 
#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];
  		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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -