oj.uz

Submission #1022419

# Submission time Handle Problem Language Result Execution time Memory
1022419 2024-07-13T13:25:27 Z CodeLakVN Zoltan (COCI16_zoltan) C++17
140 / 140
 189 ms 16332 KB 
#include <bits/stdc++.h>
using namespace std;

#define Task "ZOLTAN"
#define ll long long
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define F first
#define S second

typedef pair<int, int> ii;

const int N = 2e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }

template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }

int n;
int a[N];
vector<int> vals;

void compress() {
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    FOR(i, 1, n) a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
}

struct SegmentTree {
    int n;
    vector<ii> maxVal;

    SegmentTree(int _n = 0) {
        n = _n;
        maxVal.assign(4 * n + 10, {0, 0});
    }

    ii combine(ii x, ii y) {
        if (x.F > y.F) return x;
        if (y.F > x.F) return y;
        return {x.F, (x.S + y.S) % MOD};
    }

    void update(int id, int l, int r, int pos, ii val) {
        if (l == r) {
            maxVal[id] = combine(maxVal[id], val);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(2 * id, l, mid, pos, val);
        else update(2 * id + 1, mid + 1, r, pos, val);
        maxVal[id] = combine(maxVal[2 * id], maxVal[2 * id + 1]);
    }

    ii get(int id, int l, int r, int u, int v) {
        if (l > v || r < u) return {0, 0};
        if (l >= u && r <= v) return maxVal[id];
        int mid = (l + r) >> 1;
        return combine(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v));
    }

    void update(int pos, ii val) {
        update(1, 1, n, pos, val);
    }

    ii get(int u, int v) {
        return get(1, 1, n, u, v);
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")) {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }

    cin >> n;
    FOR(i, 1, n) cin >> a[i], vals.push_back(a[i]);

    compress();
    int m = vals.size();

    SegmentTree LIS(m), LDS(m);

    int ansLen = 0, ansCnt = 0;
    FOD(i, n, 1) {
        ii curLIS = LIS.get(a[i] + 1, m);
        ii curLDS = LDS.get(1, a[i] - 1);
        curLIS.F++;
        curLDS.F++;
        if (curLIS.F == 1) curLIS.S = 1;
        if (curLDS.F == 1) curLDS.S = 1;

        if (maximize(ansLen, curLIS.F + curLDS.F - 1))
            ansCnt = 1LL * curLIS.S * curLDS.S % MOD;
        else if (ansLen == curLIS.F + curLDS.F - 1)
            ansCnt = (ansCnt + 1LL * curLDS.S * curLIS.S % MOD) % MOD;
        LIS.update(a[i], curLIS);
        LDS.update(a[i], curLDS);
    }

    FOR(i, 1, n - ansLen) ansCnt = (ansCnt * 2) % MOD;

    cout << ansLen << " " << ansCnt;
    return 0;
}

Compilation message

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

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 416 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 468 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 97 ms 12816 KB Output is correct
12 Correct 85 ms 11304 KB Output is correct
13 Correct 80 ms 10460 KB Output is correct
14 Correct 117 ms 11468 KB Output is correct
15 Correct 149 ms 14280 KB Output is correct
16 Correct 189 ms 16332 KB Output is correct
17 Correct 126 ms 13772 KB Output is correct
18 Correct 123 ms 13776 KB Output is correct
19 Correct 129 ms 13776 KB Output is correct
20 Correct 122 ms 14004 KB Output is correct