oj.uz

Submission #892556

# Submission time Handle Problem Language Result Execution time Memory
892556 2023-12-25T13:42:36 Z therealpain Financial Report (JOI21_financial) C++17
17 / 100
 242 ms 30452 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x) (((x) >> (i)) & 1)
#define TASK ""
 
using namespace std;
 
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) a = b; else return false; return true;
}
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) a = b; else return false; return true;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
 
int n;
int d;
int a[N];
 
namespace subtask2 {
    int dp[405][405];
    vector <int> value;
 
    void solve() {
        for (int i = 1; i <= n; ++i) value.push_back(a[i]);
 
        sort(all(value));
        value.erase(unique(all(value)), value.end());
        int m = (int) value.size();
 
        for (int i = 1; i <= n; ++i) {
            a[i] = lower_bound(all(value), a[i]) - value.begin() + 1;
        }
 
        memset(dp, -0x3f, sizeof dp);
 
        for (int i = 1; i <= n; ++i) dp[i][a[i]] = 1;
 
        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= max(i - d, 1); --j) {
                for (int mx = 1; mx <= m; ++mx) {
                    maxi(dp[i][max(mx, a[i])], dp[j][mx] + (mx < a[i]));
                }
            }
        }
 
        cout << *max_element(dp[n] + 1, dp[n] + m + 1);
    }
};

namespace subtask3 {
    vector <int> value;
    int dp[7005][7005];
    deque <int> dq[7005];
 
    void solve() {
        for (int i = 1; i <= n; ++i) value.push_back(a[i]);
 
        sort(all(value));
        value.erase(unique(all(value)), value.end());
        int m = (int) value.size();
 
        for (int i = 1; i <= n; ++i) {
            a[i] = lower_bound(all(value), a[i]) - value.begin() + 1;
        }
 
        memset(dp, -0x3f, sizeof dp);
 
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                while (dq[j].size() && dq[j].front() + d < i) dq[j].pop_front();
 
                if (dq[j].size()) maxi(dp[i][max(a[i], j)], dp[dq[j].front()][j] + (a[i] > j));
 
                while (dq[max(j, a[i])].size() && dp[dq[max(j, a[i])].back()][max(j, a[i])] <= dp[i][j])
                    dq[max(j, a[i])].pop_back();
 
                dq[max(a[i], j)].push_back(i);
 
            }
 
            maxi(dp[i][a[i]], 1);
            dq[a[i]].push_back(i);
        }
 
 
        //for (int i = 1; i <= n; ++i)
 
        cout << *max_element(dp[n] + 1, dp[n] + m + 1);
    }
};

 
namespace subtask4 {
    stack <int> st;
 
    void solve() {
        int ans = 0;
        for (int i = n; i >= 1; --i) {
            while (st.size() && st.top() <= a[i]) st.pop();
            st.push(a[i]);
            maxi(ans, st.size());
        }
        cout << ans;
    }
};
 
namespace subtask5 {
    void solve() {
        vector <int> dp;
 
        for (int i = 1; i <= n; ++i) {
            int p = lower_bound(all(dp), a[i]) - dp.begin();
            if (p == dp.size()) dp.push_back(a[i]);
            else dp[p] = a[i];
        }
 
        cout << (int) dp.size() << '\n';
    }
};

namespace subtask6 {
    int dp[N];
    int m[N];
    int r[N];
    pair <int, int> b[N];

    struct IntervalTree {
        int st[N << 2];

        void init(int value) {
            for (int i = 1; i <= n * 4; ++i) st[i] = value;
        }


        void update(int id, int l, int r, int i, int value) {
            if (l > i || r < i) return;
            if (l == r) {
                st[id] = value;
                return;
            }

            int mid = l + r >> 1;
            update(id << 1, l, mid, i, value);
            update(id << 1 | 1, mid + 1, r, i, value);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }

        int get(int id, int l, int r, int u, int v) {
            if (l > v || r < u) return -1e9;
            if (u <= l && r <= v) return st[id];

            int mid = l + r >> 1;
            return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
        }

        int walk(int id, int l, int r, int u, int v, int value) {
            if (l > v || r < u) return -1;
            if (u <= l && r <= v) {
                if (st[id] <= value) return -1;

                while (l < r) {
                    int mid = l + r >> 1;
                    if (st[id << 1] > value) {
                        id = id << 1;
                        r = mid;
                    } else {
                        id = (id << 1) | 1;
                        l = mid + 1;
                    }
                }

                return l;
            }

            int mid = l + r >> 1;
            int res = walk(id << 1, l, mid, u, v, value);
            if (res == -1) return walk(id << 1 | 1, mid + 1, r, u, v, value);
            return res;
        }
    };

    void solve() {
        IntervalTree IT1, IT2, IT3;
        IT1.init(-1e9);
        IT2.init(-1e9);
        IT3.init(-1e9);
        for (int i = 1; i <= n; ++i) IT1.update(1, 1, n, i, a[i]);

        for (int i = n; i - d >= 1; --i) {
            m[i] = IT1.get(1, 1, n, i - d, i);
            IT2.update(1, 1, n, i, m[i]);
        }


        for (int i = n; i >= 1; --i) {
            if (i + d <= n) {
                int res = IT2.walk(1, 1, n, i + d, n, a[i]);
                //cout << res << " \n"[i == n];

                r[i] = (res == -1 ? n : res);
            } else {
                r[i] = n;
            }

            //cout << IT2.get(1, 1, n, i, i) << ' ';
        }


        //cout << '\n';
        for (int i = 1; i <= n; ++i) {
            b[i] = make_pair(a[i], i);
            //cout << r[i] << ' ';
        }

        //cout << '\n';

        sort(b + 1, b + n + 1, [](pair <int, int> x, pair <int, int> y) {
            return (x.fi > y.fi) || (x.fi == y.fi && x.se < y.se);
        });

        memset(dp, -0x3f, sizeof dp);

        for (int i = 1; i <= n; ++i) {
            int pos = b[i].se;
            int cur = max(IT3.get(1, 1, n, pos + 1, r[pos]), 0) + 1;
            dp[pos] = cur;
            IT3.update(1, 1, n, pos, dp[pos]);
        }

        cout << *max_element(dp, dp + n + 1);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);
    cin >> n >> d;
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    //if (n <= 400) subtask2::solve();
    // if (n <= 7000) subtask3::solve();
    // else if (d == 1) subtask4::solve();
    // else if (d == n) subtask5::solve();
    subtask6::solve();
}

Compilation message

Main.cpp: In function 'void subtask5::solve()':
Main.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             if (p == dp.size()) dp.push_back(a[i]);
      |                 ~~^~~~~~~~~~~~
Main.cpp: In member function 'void subtask6::IntervalTree::update(int, int, int, int, int)':
Main.cpp:149:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  149 |             int mid = l + r >> 1;
      |                       ~~^~~
Main.cpp: In member function 'int subtask6::IntervalTree::get(int, int, int, int, int)':
Main.cpp:159:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  159 |             int mid = l + r >> 1;
      |                       ~~^~~
Main.cpp: In member function 'int subtask6::IntervalTree::walk(int, int, int, int, int, int)':
Main.cpp:169:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |                     int mid = l + r >> 1;
      |                               ~~^~~
Main.cpp:182:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  182 |             int mid = l + r >> 1;
      |                       ~~^~~
Main.cpp: In instantiation of 'bool maxi(T1&, T2) [with T1 = int; T2 = long unsigned int]':
Main.cpp:108:32:   required from here
Main.cpp:11:11: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   11 |     if (a < b) a = b; else return false; return true;
      |         ~~^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26712 KB Output is correct
2 Correct 10 ms 26716 KB Output is correct
3 Correct 9 ms 26728 KB Output is correct
4 Correct 9 ms 26716 KB Output is correct
5 Correct 11 ms 26716 KB Output is correct
6 Correct 10 ms 26824 KB Output is correct
7 Correct 10 ms 26716 KB Output is correct
8 Correct 10 ms 26716 KB Output is correct
9 Correct 12 ms 26716 KB Output is correct
10 Correct 10 ms 26804 KB Output is correct
11 Correct 10 ms 26716 KB Output is correct
12 Correct 10 ms 26716 KB Output is correct
13 Correct 10 ms 26716 KB Output is correct
14 Correct 11 ms 26712 KB Output is correct
15 Correct 10 ms 26716 KB Output is correct
16 Correct 10 ms 26748 KB Output is correct
17 Correct 9 ms 26716 KB Output is correct
18 Correct 10 ms 26716 KB Output is correct
19 Correct 10 ms 26716 KB Output is correct
20 Correct 11 ms 26704 KB Output is correct
21 Incorrect 14 ms 26716 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26712 KB Output is correct
2 Correct 10 ms 26716 KB Output is correct
3 Correct 9 ms 26728 KB Output is correct
4 Correct 9 ms 26716 KB Output is correct
5 Correct 11 ms 26716 KB Output is correct
6 Correct 10 ms 26824 KB Output is correct
7 Correct 10 ms 26716 KB Output is correct
8 Correct 10 ms 26716 KB Output is correct
9 Correct 12 ms 26716 KB Output is correct
10 Correct 10 ms 26804 KB Output is correct
11 Correct 10 ms 26716 KB Output is correct
12 Correct 10 ms 26716 KB Output is correct
13 Correct 10 ms 26716 KB Output is correct
14 Correct 11 ms 26712 KB Output is correct
15 Correct 10 ms 26716 KB Output is correct
16 Correct 10 ms 26748 KB Output is correct
17 Correct 9 ms 26716 KB Output is correct
18 Correct 10 ms 26716 KB Output is correct
19 Correct 10 ms 26716 KB Output is correct
20 Correct 11 ms 26704 KB Output is correct
21 Incorrect 14 ms 26716 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26712 KB Output is correct
2 Correct 10 ms 26716 KB Output is correct
3 Correct 9 ms 26728 KB Output is correct
4 Correct 9 ms 26716 KB Output is correct
5 Correct 11 ms 26716 KB Output is correct
6 Correct 10 ms 26824 KB Output is correct
7 Correct 10 ms 26716 KB Output is correct
8 Correct 10 ms 26716 KB Output is correct
9 Correct 12 ms 26716 KB Output is correct
10 Correct 10 ms 26804 KB Output is correct
11 Correct 10 ms 26716 KB Output is correct
12 Correct 10 ms 26716 KB Output is correct
13 Correct 10 ms 26716 KB Output is correct
14 Correct 11 ms 26712 KB Output is correct
15 Correct 10 ms 26716 KB Output is correct
16 Correct 10 ms 26748 KB Output is correct
17 Correct 9 ms 26716 KB Output is correct
18 Correct 10 ms 26716 KB Output is correct
19 Correct 10 ms 26716 KB Output is correct
20 Correct 11 ms 26704 KB Output is correct
21 Incorrect 14 ms 26716 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 30032 KB Output is correct
2 Correct 222 ms 30032 KB Output is correct
3 Correct 230 ms 29948 KB Output is correct
4 Correct 242 ms 30028 KB Output is correct
5 Correct 220 ms 30192 KB Output is correct
6 Correct 238 ms 30048 KB Output is correct
7 Correct 179 ms 30032 KB Output is correct
8 Correct 199 ms 30036 KB Output is correct
9 Correct 186 ms 29964 KB Output is correct
10 Correct 205 ms 30028 KB Output is correct
11 Correct 224 ms 30032 KB Output is correct
12 Correct 229 ms 30048 KB Output is correct
13 Correct 220 ms 30016 KB Output is correct
14 Correct 240 ms 30032 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 30032 KB Output is correct
2 Correct 148 ms 30036 KB Output is correct
3 Correct 164 ms 30036 KB Output is correct
4 Correct 163 ms 30444 KB Output is correct
5 Correct 148 ms 30032 KB Output is correct
6 Correct 161 ms 30032 KB Output is correct
7 Correct 117 ms 30192 KB Output is correct
8 Correct 108 ms 30028 KB Output is correct
9 Correct 115 ms 30188 KB Output is correct
10 Correct 144 ms 30032 KB Output is correct
11 Correct 168 ms 30452 KB Output is correct
12 Correct 146 ms 30036 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26712 KB Output is correct
2 Correct 10 ms 26716 KB Output is correct
3 Correct 9 ms 26728 KB Output is correct
4 Correct 9 ms 26716 KB Output is correct
5 Correct 11 ms 26716 KB Output is correct
6 Correct 10 ms 26824 KB Output is correct
7 Correct 10 ms 26716 KB Output is correct
8 Correct 10 ms 26716 KB Output is correct
9 Correct 12 ms 26716 KB Output is correct
10 Correct 10 ms 26804 KB Output is correct
11 Correct 10 ms 26716 KB Output is correct
12 Correct 10 ms 26716 KB Output is correct
13 Correct 10 ms 26716 KB Output is correct
14 Correct 11 ms 26712 KB Output is correct
15 Correct 10 ms 26716 KB Output is correct
16 Correct 10 ms 26748 KB Output is correct
17 Correct 9 ms 26716 KB Output is correct
18 Correct 10 ms 26716 KB Output is correct
19 Correct 10 ms 26716 KB Output is correct
20 Correct 11 ms 26704 KB Output is correct
21 Incorrect 14 ms 26716 KB Output isn't correct
22 Halted 0 ms 0 KB -