oj.uz

Submission #647443

# Submission time Handle Problem Language Result Execution time Memory
647443 2022-10-02T15:21:29 Z LeonaRaging Feast (NOI19_feast) C++14
12 / 100
 1000 ms 15996 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 3e5 + 4;
const int INF = 1e9;

using T = pair<int,int>;

int n, k, a[maxn], par[maxn], Rank[maxn];

priority_queue<T, vector<T>, greater<T>> pq;
vector<int> myVec;
set<int> ms;

struct DisjointSet {
    DisjointSet(int n) {
        for (int i = 1; i <= n; i++) {
            par[i] = i, Rank[i] = myVec[i - 1];
            pq.push({abs(Rank[i]), i});
            ms.insert(i);
        }
    }
    int find(int x) {
        if (x != par[x]) par[x] = find(par[x]);
        return par[x];
    }
    bool join(int u, int v) {
        if (u == v) return 0;
        ms.erase(v);
        Rank[u] += Rank[v];
        par[v] = u;
        return 1;
    }
};

void init() {
    while (Rank[*ms.begin()] < 0)
        ms.erase(*ms.begin());  
    while (Rank[*ms.rbegin()] < 0)
        ms.erase(*ms.rbegin());
}

signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int cur = 0, cnt = 0;
    int L = 1, R = n;
    while (a[L] < 0) L++;
    while (a[R] < 0) R--;
    int flag = (a[L] > 0 ? 1 : -1);
    for (int i = L; i <= R + 1; i++) {
        if (a[i] * flag < 0 || i == R + 1) {
            if (cur > 0)
                cnt++;
            myVec.pb(cur);
            cur = 0;
            flag = (a[i] > 0 ? 1 : -1);
        }
        cur += a[i];
    }
    n = myVec.size();
    DisjointSet Dsu(n);
    while (cnt > k) {
        int cur, x; tie(cur, x) = pq.top(); pq.pop();
        if (ms.find(x) == ms.end()) continue;
        auto lo = ms.lower_bound(x);
        auto hi = ms.upper_bound(x);
        int u = (lo == ms.begin() ? x : *(--lo));
        int v = (hi == ms.end() ? x : *hi);
        u = Dsu.find(u); v = Dsu.find(v);
        int pre = (Rank[u] > 0 && u != x) + (Rank[v] > 0 && v != x) + (Rank[x] > 0);
        Dsu.join(x, u);  
        Dsu.join(x, v);
        pq.push({abs(Rank[u]), u});
        // for (auto i : ms) clog << i << ' '; 
        // clog << '\n';
        int suf = Rank[u] > 0;
        cnt -= (pre - suf);
        init();
        // clog << db(x) << db(u) << db(v) << '\n';
    }
    int res = 0;
    for (auto i : ms)
        if (Rank[i] > 0) res += Rank[i];
    cout << res;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2456 KB Output is correct
2 Correct 106 ms 2548 KB Output is correct
3 Correct 107 ms 2552 KB Output is correct
4 Correct 109 ms 2508 KB Output is correct
5 Correct 106 ms 2628 KB Output is correct
6 Correct 103 ms 2580 KB Output is correct
7 Correct 103 ms 2508 KB Output is correct
8 Correct 107 ms 2548 KB Output is correct
9 Correct 105 ms 2576 KB Output is correct
10 Correct 111 ms 2584 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2520 KB Output is correct
2 Correct 58 ms 3740 KB Output is correct
3 Correct 55 ms 3584 KB Output is correct
4 Correct 58 ms 3624 KB Output is correct
5 Correct 108 ms 4840 KB Output is correct
6 Correct 61 ms 3640 KB Output is correct
7 Correct 60 ms 3664 KB Output is correct
8 Correct 106 ms 4872 KB Output is correct
9 Correct 109 ms 4872 KB Output is correct
10 Correct 58 ms 3684 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 15996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2456 KB Output is correct
2 Correct 106 ms 2548 KB Output is correct
3 Correct 107 ms 2552 KB Output is correct
4 Correct 109 ms 2508 KB Output is correct
5 Correct 106 ms 2628 KB Output is correct
6 Correct 103 ms 2580 KB Output is correct
7 Correct 103 ms 2508 KB Output is correct
8 Correct 107 ms 2548 KB Output is correct
9 Correct 105 ms 2576 KB Output is correct
10 Correct 111 ms 2584 KB Output is correct
11 Correct 56 ms 2520 KB Output is correct
12 Correct 58 ms 3740 KB Output is correct
13 Correct 55 ms 3584 KB Output is correct
14 Correct 58 ms 3624 KB Output is correct
15 Correct 108 ms 4840 KB Output is correct
16 Correct 61 ms 3640 KB Output is correct
17 Correct 60 ms 3664 KB Output is correct
18 Correct 106 ms 4872 KB Output is correct
19 Correct 109 ms 4872 KB Output is correct
20 Correct 58 ms 3684 KB Output is correct
21 Execution timed out 1092 ms 15996 KB Time limit exceeded
22 Halted 0 ms 0 KB -