oj.uz

Submission #486953

# Submission time Handle Problem Language Result Execution time Memory
486953 2021-11-13T14:18:18 Z KienTran Feast (NOI19_feast) C++14
4 / 100
 114 ms 134140 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 92 ms 134128 KB Output is correct
2 Correct 111 ms 134076 KB Output is correct
3 Correct 108 ms 134024 KB Output is correct
4 Correct 114 ms 134084 KB Output is correct
5 Correct 95 ms 134044 KB Output is correct
6 Correct 90 ms 134064 KB Output is correct
7 Correct 88 ms 133968 KB Output is correct
8 Correct 92 ms 133996 KB Output is correct
9 Correct 90 ms 133948 KB Output is correct
10 Correct 87 ms 134140 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 134084 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 92 ms 134128 KB Output is correct
2 Correct 111 ms 134076 KB Output is correct
3 Correct 108 ms 134024 KB Output is correct
4 Correct 114 ms 134084 KB Output is correct
5 Correct 95 ms 134044 KB Output is correct
6 Correct 90 ms 134064 KB Output is correct
7 Correct 88 ms 133968 KB Output is correct
8 Correct 92 ms 133996 KB Output is correct
9 Correct 90 ms 133948 KB Output is correct
10 Correct 87 ms 134140 KB Output is correct
11 Correct 95 ms 134072 KB Output is correct
12 Incorrect 85 ms 134044 KB Output isn't correct
13 Halted 0 ms 0 KB -