Submission #231428

#	Time	Username	Problem	Language	Result	Execution time	Memory
231428		maskoff	Bigger segments (IZhO19_segments)	C++14	0 / 100	4 ms	384 KiB

segments

#include <bits/stdc++.h>
#include <ext/rope>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair

#define pss pair<line*, line*>
#define pptreap pair<treap*, treap*>
 
using namespace std;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
                                    
const ll inf = 1e16;
const int MOD = 1e9 + 7;
                                          
const int dx[] = {+1, -1, 0, 0};
const int dy[] = {0, 0, +1, -1};

int const N = 7e6;

struct treap {
	ll x, y;
	pii mx;
	treap *l, *r;
	treap(ll new_x, int new_mx, int pos) {
		x = new_x;
		y = (rand() << 15) | rand();
		mx = {new_mx, pos};
		l = r = nullptr;
	}
};

pii getmx(treap *a) {
	if (a == nullptr)
		return {-1e9, -1e9};
  return a -> mx;
}

void update(treap *&a) {
	a->mx = max(a->mx, max(getmx(a->l), getmx(a->r)));
}

treap* merge(treap *t1, treap *t2) {
	if (t1 == nullptr)
		return t2;
	if (t2 == nullptr)
		return t1;
	if (t1->y > t2->y) {
		t1->r = merge(t1->r, t2);
		update(t1);
		return t1;
	}
	else {
		t2->l = merge(t1, t2->l);
		update(t2);
		return t2;
	}
}

pptreap split(treap *t, ll k) {
	if (t == nullptr)
		return mp(nullptr, nullptr);
	if (t->x <= k) {
		pptreap cnt = split(t->r, k);
		t->r = cnt.fr;
		update(t);
		return mp(t, cnt.sc);
	}
	else {
		pptreap cnt = split(t->l, k);
		t->l = cnt.sc;
		update(t);
		return mp(cnt.fr, t);
	}
} 

int main() {      
	ios_base :: sync_with_stdio(false);
  cin.tie(nullptr);
  srand(time(NULL));
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++)
  	cin >> a[i];
  vector<ll> dp(n + 1), sum(n + 1), pref(n + 1);
  for (int i = 1; i <= n; i++)
  	pref[i] = pref[i - 1] + a[i];
  treap* t = new treap (0, 0, 0);
  for (int i = 1; i <= n; i++) {	
  	pptreap k = split (t, pref[i]);
  	pii pos = getmx(k.fr);
  	t = merge(k.fr, k.sc);

  	dp[i] = pos.fr + 1;
  	sum[i] = pref[i] - pref[pos.sc];

  	treap* nw = new treap (sum[i] + pref[i], dp[i], i);

  	k = split(t, sum[i] + pref[i]);
  	t = merge(merge(k.fr, nw), k.sc);
  }
  cout << dp[n];
	return 0;
}

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