Submission #231473

#	Time	Username	Problem	Language	Result	Execution time	Memory
231473		maskoff	Bigger segments (IZhO19_segments)	C++14	100 / 100	596 ms	49040 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
 
#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;
 
int const N = 7e6;
 
struct treap {
    ll x, y;
    pii mx, val;
    treap *l, *r;
    treap(ll new_x, ll new_mx, ll pos) {
        x = new_x;
        y = (rand() << 15) | rand();
        mx = {new_mx, pos};
        val = {new_mx, pos};
        l = r = nullptr;
    }
};
 
pii getmx(treap *a) {
    if (a == nullptr)
        return {0, 0};
    return a->mx;
}
 
void update(treap *&a) {
    a->mx = max(a->val, 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);
    }
}
 
bool exist(treap *t, ll pos, pii new_val) {
	if (t == nullptr)
		return 0;
	if (pos < t->x)
		return exist(t->l, pos, new_val);
	if (pos > t->x)
		return exist(t->r, pos, new_val);
	if (pos == t->x) {
		t->val = max(t->val, new_val);
		t->mx = max(t->mx, t->val);
		return 1;
	}
	update(t);
}
 
void data() {
    #ifdef PC
        freopen("rofl.in", "r", stdin);
        freopen("rofl.out", "w", stdout);
    #endif
}
 
int main() {
	data();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(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);
 
		if (!exist(t, sum[i] + pref[i], mp(dp[i], i))) {
	        k = split(t, sum[i] + pref[i]);
	        t = merge(merge(k.fr, nw), k.sc);			
		}
    }
    cout << dp[n];
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'bool exist(treap*, ll, pii)':
segments.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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