oj.uz

Submission #1022505

# Submission time Handle Problem Language Result Execution time Memory
1022505 2024-07-13T15:40:25 Z lmToT27 Zoltan (COCI16_zoltan) C++14
21 / 140
 94 ms 16336 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 = 1; i <= n; 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
21.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 472 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't 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 Incorrect 1 ms 476 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 51 ms 12716 KB Output isn't correct
12 Incorrect 44 ms 11224 KB Output isn't correct
13 Incorrect 39 ms 10708 KB Output isn't correct
14 Incorrect 61 ms 11544 KB Output isn't correct
15 Incorrect 80 ms 14260 KB Output isn't correct
16 Incorrect 94 ms 16336 KB Output isn't correct
17 Incorrect 57 ms 14796 KB Output isn't correct
18 Incorrect 57 ms 14860 KB Output isn't correct
19 Incorrect 58 ms 14796 KB Output isn't correct
20 Incorrect 62 ms 14700 KB Output isn't correct