oj.uz

Submission #689668

# Submission time Handle Problem Language Result Execution time Memory
689668 2023-01-29T05:13:21 Z lohacho Catfish Farm (IOI22_fish) C++17
6 / 100
 540 ms 61736 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;
        st = 0;
    }

    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;

        // for(int i = 1; i <= N; ++i){
        //     cout << dp2.get(1, 0, mx, i + dp1.st, i + dp1.st) << ' ';
        // }
        // cout << endl;
        ans = max(ans, dp2.get(1, 0, mx, 0, mx));
        if(i < N - 1){
            ans = max(ans, dp1.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:40:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         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:54:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         long long m = s + e >> 1;
      |                       ~~^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 40708 KB Output is correct
2 Correct 249 ms 46032 KB Output is correct
3 Correct 27 ms 37840 KB Output is correct
4 Correct 22 ms 37860 KB Output is correct
5 Correct 434 ms 61736 KB Output is correct
6 Incorrect 540 ms 61644 KB 1st lines differ - on the 1st token, expected: '300000000000000', found: '237815000000000'
7 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 296 ms 47104 KB Output is correct
3 Correct 371 ms 53732 KB Output is correct
4 Correct 142 ms 40708 KB Output is correct
5 Correct 169 ms 45872 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 22 ms 37872 KB Output is correct
11 Correct 22 ms 37792 KB Output is correct
12 Correct 140 ms 41828 KB Output is correct
13 Correct 177 ms 47448 KB Output is correct
14 Correct 147 ms 41848 KB Output is correct
15 Correct 174 ms 46540 KB Output is correct
16 Correct 144 ms 41880 KB Output is correct
17 Correct 170 ms 46492 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37888 KB Output is correct
2 Correct 21 ms 37844 KB Output is correct
3 Incorrect 82 ms 38652 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '12017166175977'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114945503427'
10 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 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114945503427'
10 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 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114945503427'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37888 KB Output is correct
2 Correct 21 ms 37844 KB Output is correct
3 Incorrect 82 ms 38652 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '12017166175977'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 40708 KB Output is correct
2 Correct 249 ms 46032 KB Output is correct
3 Correct 27 ms 37840 KB Output is correct
4 Correct 22 ms 37860 KB Output is correct
5 Correct 434 ms 61736 KB Output is correct
6 Incorrect 540 ms 61644 KB 1st lines differ - on the 1st token, expected: '300000000000000', found: '237815000000000'
7 Halted 0 ms 0 KB -