oj.uz

Submission #231424

# Submission time Handle Problem Language Result Execution time Memory
231424 2020-05-13T15:12:59 Z maskoff Bigger segments (IZhO19_segments) C++14
0 / 100
 5 ms 384 KB 
#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, ll new_mx, ll 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() {                 
#ifdef Mask                                                         
  freopen(".in", 	"r", stdin);
  freopen(".out", "w", stdout);  
#endif
	ios_base :: sync_with_stdio(false);
  cin.tie(nullptr);
  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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -