oj.uz

Submission #689658

# Submission time Handle Problem Language Result Execution time Memory
689658 2023-01-29T04:59:03 Z lohacho Catfish Farm (IOI22_fish) C++17
12 / 100
 639 ms 68036 KB 
#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

struct Seg{
    long long n, st;

    vector<long long> tr, lazy;

    Seg(long long m):n(m + 4){
        tr.resize(n * 4 * 3, -(long long)1e18);
        lazy.resize(n * 4 * 3, -(long long)1e18);
        st = n;
    }

    void update(int x, int s, int e){
        tr[x] = max(tr[x], lazy[x]);
        if(s < e){
            lazy[x * 2] = max(lazy[x * 2], lazy[x]);
            lazy[x * 2 + 1] = max(lazy[x * 2 + 1], lazy[x]);
        }
        lazy[x] = -(long long)1e18;
    }

    void push(long long x, long long s, long long e, int ps, int pe, long long val){
        if(pe < s || ps > e){
            return;
        }
        if(ps <= s && pe >= e){
            lazy[x] = max(lazy[x], val);
            update(x, s, e);
            return;
        }

        update(x, s, e);

        int m = s + e >> 1;
        push(x * 2, s, m, ps, pe, val);
        push(x * 2 + 1, m + 1, e, ps, pe, val);

        tr[x] = max(tr[x * 2], tr[x * 2 + 1]);
    }

    long long get(long long x, long long s, long long e, long long fs, long long fe){
        if(fe < s || fs > e || fs > fe) return -(long long)1e18;
        update(x, s, e);
        if(fs <= s && fe >= e){
            return tr[x];
        }

        long long m = s + e >> 1;

        return max(get(x * 2, s, m, fs, fe), get(x * 2 + 1, m + 1, e, fs, fe));
    }
};

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

    vector<vector<long long>> a(M);
    for(long long i = 0; i < M; ++i){
        a[i] = {X[i], Y[i] + 1, W[i]};
    }

    sort(a.begin(), a.end());

    Seg dp1(N), dp2(N);

    int mx = N * 3 + 1;
    //cout << mx << endl;
    dp1.push(1, 0, mx, 0, mx, 0);

    long long ans = 0;

    for(long long i = 0, j = 0; i < N; ++i){
        long long hval = dp1.get(1, 0, mx, 0, mx);

        dp1.push(1, 0, mx, 0, mx, dp2.get(1, 0, mx, 0, mx));

        long long l = j, r = j - 1;
        while(r + 1 < M && a[r + 1][0] == i){
            ++r;
        }

        //cout << i << ' ' << l << ' ' << r << endl;

        dp1.st -= 1;
        dp2.st += 1;
        for(long long x = l; x <= r; ++x){
            dp1.push(1, 0, mx, a[x][1] + dp1.st, mx, dp1.get(1, 0, mx, a[x][1] + dp1.st, a[x][1] + dp1.st) + a[x][2]);
        }
        for(long long x = r; x >= l; --x){
            dp2.push(1, 0, mx, 0, a[x][1] + dp2.st, dp2.get(1, 0, mx, a[x][1] + dp2.st, a[x][1] + dp2.st) + a[x][2]);
        }

        dp2.push(1, 0, mx, 0, mx, hval);

        j = r + 1;

        // for(int i = 1; i <= N; ++i){
        //     cout << dp1.get(1, 0, mx, i + dp1.st, i + dp1.st) << ' ';
        // }
        // cout << endl;
        if(i < N - 1){
            ans = max(ans, dp1.get(1, 0, mx, 0, mx));
        }
        else{
            ans = max(ans, dp2.get(1, 0, mx, 0, mx));
        }
    }
    ans = max(ans, dp2.get(1, 0, mx, 0, mx));

    return ans;
}

Compilation message

fish.cpp: In member function 'void Seg::push(long long int, long long int, long long int, int, int, long long int)':
fish.cpp:39:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int m = s + e >> 1;
      |                 ~~^~~
fish.cpp: In member function 'long long int Seg::get(long long int, long long int, long long int, long long int, long long int)':
fish.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         long long m = s + e >> 1;
      |                       ~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 41836 KB Output is correct
2 Correct 174 ms 47448 KB Output is correct
3 Correct 20 ms 37844 KB Output is correct
4 Correct 20 ms 37844 KB Output is correct
5 Correct 542 ms 67740 KB Output is correct
6 Correct 639 ms 68036 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 292 ms 49628 KB Output is correct
3 Correct 352 ms 57020 KB Output is correct
4 Correct 144 ms 41840 KB Output is correct
5 Correct 171 ms 47448 KB Output is correct
6 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
7 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37864 KB Output is correct
2 Correct 22 ms 37768 KB Output is correct
3 Correct 96 ms 39224 KB Output is correct
4 Correct 76 ms 41300 KB Output is correct
5 Correct 170 ms 47272 KB Output is correct
6 Correct 182 ms 46540 KB Output is correct
7 Correct 193 ms 47248 KB Output is correct
8 Correct 171 ms 47280 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37864 KB Output is correct
2 Correct 22 ms 37768 KB Output is correct
3 Correct 96 ms 39224 KB Output is correct
4 Correct 76 ms 41300 KB Output is correct
5 Correct 170 ms 47272 KB Output is correct
6 Correct 182 ms 46540 KB Output is correct
7 Correct 193 ms 47248 KB Output is correct
8 Correct 171 ms 47280 KB Output is correct
9 Correct 165 ms 47040 KB Output is correct
10 Correct 177 ms 28544 KB Output is correct
11 Correct 331 ms 57020 KB Output is correct
12 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
13 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 41836 KB Output is correct
2 Correct 174 ms 47448 KB Output is correct
3 Correct 20 ms 37844 KB Output is correct
4 Correct 20 ms 37844 KB Output is correct
5 Correct 542 ms 67740 KB Output is correct
6 Correct 639 ms 68036 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 292 ms 49628 KB Output is correct
9 Correct 352 ms 57020 KB Output is correct
10 Correct 144 ms 41840 KB Output is correct
11 Correct 171 ms 47448 KB Output is correct
12 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
13 Halted 0 ms 0 KB -