oj.uz

Submission #486951

# Submission time Handle Problem Language Result Execution time Memory
486951 2021-11-13T14:13:39 Z KienTran Feast (NOI19_feast) C++14
4 / 100
 110 ms 136952 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 3e5 + 5;
const int inf = 1e18;

int n, k, a[O], lazy[O * 4];

struct Node{
    int sum, l, r, w, pref, suf, lsuf, rpref;
} tree[O * 4], rtree[O * 4];

Node Merg(Node x, Node y){
    Node root; root.w = -inf;
    root.sum = x.sum + y.sum;

    root.pref = x.pref + (x.pref == x.sum ? max(0ll, y.pref) : 0);
    root.rpref = (x.pref == x.sum && y.pref > 0) ? y.rpref : x.rpref;

    root.suf = y.suf + (y.suf == y.sum ? max(0ll, x.suf) : 0);
    root.lsuf = (y.suf == y.sum && x.suf > 0) ? x.lsuf : y.lsuf;

    if (x.w > root.w){
        root.w = x.w;
        root.l = x.l;
        root.r = x.r;
    }

    if (y.w > root.w){
        root.w = y.w;
        root.l = y.l;
        root.r = y.r;
    }

    if (x.suf + y.pref >= root.w){
        root.w = x.suf + y.pref;
        root.l = x.lsuf;
        root.r = y.rpref;
    }

    return root;
}

void Push(int id){
    int &x = lazy[id];
    if (x == 0) return;

    for (int i = 2 * id; i <= 2 * id + 1; ++ i){
        swap(tree[i], rtree[i]);
        lazy[i] ^= x;
    }

    x = 0; return;
}

void Build(int id, int l, int r){
    if (l == r){
        tree[id] = {a[l], r, l, a[r], a[l], a[r], l, r};
        rtree[id] = {-a[r], l, r, -a[l], -a[r], -a[l], r, l};
        return;
    }
    int mid = (l + r) / 2;
    Build(id << 1, l, mid);
    Build(id << 1 | 1, mid + 1, r);
    tree[id] = Merg(tree[id << 1], tree[id << 1 | 1]);
    rtree[id] = Merg(rtree[id << 1], rtree[id << 1 | 1]);
}

void Update(int id, int l, int r, int u, int v){
    if (l > v || r < u) return;
    if (u <= l && r <= v){
        swap(tree[id], rtree[id]);
        lazy[id] ^= 1;
        return;
    }
    int mid = (l + r) / 2; Push(id);
    Update(id << 1, l, mid, u, v);
    Update(id << 1 | 1, mid + 1, r, u, v);
    tree[id] = Merg(tree[id << 1], tree[id << 1 | 1]);
    rtree[id] = Merg(rtree[id << 1], rtree[id << 1 | 1]);
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    Build(1, 1, n);

    int res = 0;
    for (int i = 1; i <= k; ++ i){
        if (tree[1].w <= 0) break;
        res += tree[1].w;
        Update(1, 1, n, tree[1].l, tree[1].r);
    }

    cout << res;
    return 0;
}

Compilation message

feast.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main(){
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 136696 KB Output is correct
2 Correct 92 ms 136764 KB Output is correct
3 Correct 91 ms 136824 KB Output is correct
4 Correct 94 ms 136808 KB Output is correct
5 Correct 89 ms 136760 KB Output is correct
6 Correct 90 ms 136760 KB Output is correct
7 Correct 88 ms 136644 KB Output is correct
8 Correct 90 ms 136836 KB Output is correct
9 Correct 110 ms 136636 KB Output is correct
10 Correct 89 ms 136772 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 135072 KB Output is correct
2 Incorrect 89 ms 135068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 136952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 136696 KB Output is correct
2 Correct 92 ms 136764 KB Output is correct
3 Correct 91 ms 136824 KB Output is correct
4 Correct 94 ms 136808 KB Output is correct
5 Correct 89 ms 136760 KB Output is correct
6 Correct 90 ms 136760 KB Output is correct
7 Correct 88 ms 136644 KB Output is correct
8 Correct 90 ms 136836 KB Output is correct
9 Correct 110 ms 136636 KB Output is correct
10 Correct 89 ms 136772 KB Output is correct
11 Correct 85 ms 135072 KB Output is correct
12 Incorrect 89 ms 135068 KB Output isn't correct
13 Halted 0 ms 0 KB -