oj.uz

답안 #231459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231459 2020-05-13T16:37:02 Z maskoff Bigger segments (IZhO19_segments) C++14
0 / 100
 6 ms 640 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

#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, int pos) {
	if (t == nullptr)
		return 0;
	if (pos < t->x)
		return exist(t->l, pos);
	if (pos > t->x)
		return exist(t->r, pos);
	if (pos == t->x)
		return 1;
}

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);

        assert(!exist(t, sum[i] + pref[i]));

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

Compilation message

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

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -