oj.uz

Submission #1022506

# Submission time Handle Problem Language Result Execution time Memory
1022506 2024-07-13T15:41:12 Z lmToT27 Zoltan (COCI16_zoltan) C++14
140 / 140
 90 ms 14544 KB 
#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 2e5 + 3;
const ll MOD[] = {1000000007, 998244353};
const ll mod = 1e9 + 7;

#define pii pair <int, ll>

int n, a[MAX];

void maximize(pii &A, pii B) {
        if (A.first < B.first) A = B;
        else if (A.first == B.first) A.second = (A.second + B.second) % mod;
}

namespace increase {
        pii bit[MAX];

        void up(int u, pii value) {
                while (u <= n) {
                        maximize(bit[u], value);
                        u += u & -u;
                }
        }

        pii get(int u) {
                pii res = {0, 1};
                while (u) {
                        maximize(res, bit[u]);
                        u -= u & -u;
                }
                res.first++;
                return res;
        }
}

namespace decrease {
        pii bit[MAX];

        void up(int u, pii value) {
                while (u) {
                        maximize(bit[u], value);
                        u -= u & -u;
                }
        }

        pii get(int u) {
                pii res = {0, 1};
                while (u <= n) {
                        maximize(res, bit[u]);
                        u += u & -u;
                }
                res.first++;
                return res;
        }
}

pii lis[MAX], lds[MAX];

void Solve() {
        cin >> n;
        vector <int> uniqValue;
        for (int i = 1; i <= n; i++) {
                cin >> a[i];
                uniqValue.push_back(a[i]);
        }

        sort(all(uniqValue));
        uniqValue.erase(unique(all(uniqValue)), uniqValue.end());

        for (int i = 1; i <= n; i++) a[i] = lower_bound(all(uniqValue), a[i]) - uniqValue.begin() + 1;

        for (int i = n; i >= 1; i--) {
                lis[i] = increase::get(a[i] - 1);
                increase::up(a[i], lis[i]);
                lds[i] = decrease::get(a[i] + 1);
                decrease::up(a[i], lds[i]);
        }
        
        int LIS = 0;
        ll cnt = 0;

        for (int i = 1; i <= n; i++) {
                if (LIS < lis[i].first + lds[i].first - 1) {
                        LIS = lis[i].first + lds[i].first - 1;
                        cnt = lis[i].second * lds[i].second % mod;
                } else if (LIS == lis[i].first + lds[i].first - 1) {
                        cnt += lis[i].second * lds[i].second % mod;
                        cnt %= mod;
                }
        }

        for (int i = LIS + 1; i <= n; i++) cnt = cnt * 2 % mod;

        cout << LIS << ' ' << cnt;
}

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        #define TASK "ZOLTAN"
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }
        
        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}

Compilation message

zoltan.cpp: In function 'int32_t main()':
zoltan.cpp:122:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:123:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 50 ms 11616 KB Output is correct
12 Correct 52 ms 10124 KB Output is correct
13 Correct 38 ms 9564 KB Output is correct
14 Correct 62 ms 10192 KB Output is correct
15 Correct 78 ms 12492 KB Output is correct
16 Correct 90 ms 14544 KB Output is correct
17 Correct 57 ms 13512 KB Output is correct
18 Correct 56 ms 13436 KB Output is correct
19 Correct 55 ms 13516 KB Output is correct
20 Correct 57 ms 13576 KB Output is correct