Submission #1022419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022419		CodeLakVN	Zoltan (COCI16_zoltan)	C++17	140 / 140	189 ms	16332 KiB

zoltan

#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 (stderr)

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 / 140