Submission #97932

#	Time	Username	Problem	Language	Result	Execution time	Memory
97932		szawinis	Zoltan (COCI16_zoltan)	C++17	21 / 140	184 ms	33792 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int N = 4e5+1;

struct Fenwick {
    vector<int> f;
    Fenwick() {}
    void clear(int n) {
        f.assign(n+2, 0);
    }
    void update(int i, int v) {
        ++i;
        while(i < f.size()) {
            f[i] += v;
            f[i] %= MOD;
            i += i & -i;
        }
    }
    int query(int i) {
        ++i;
        int ret = 0;
        while(i > 0) {
            ret += f[i];
            ret %= MOD;
            i -= i & -i;
        }
        return ret;
    }
};

int len[N];
vector<int> f, ls[N];
Fenwick dp[N];

pair<int, int> count_LIS(vector<int> a) {
    fill(len, len+a.size()+1, 0);

    int LIS = 0;
    for(int i = 0; i < a.size(); i++) {
        int x = a[i];
        auto it = lower_bound(f.begin(), f.end(), x);
        len[i] = it - f.begin() + 1;
        LIS = max(len[i], LIS);
        if(it == f.end())
            f.push_back(x);
        else
            *it = x;
    }
    ls[0].push_back(0);
    for(int i = 0; i < a.size(); i++)
        ls[len[i]].push_back(a[i]);
    for(int i = 0; i <= a.size(); i++) {
        sort(ls[i].begin(), ls[i].end());
        ls[i].resize(unique(ls[i].begin(), ls[i].end()) - ls[i].begin());
    }
    for(int i = 0; i <= a.size(); i++) {
        dp[i].clear(ls[i].size() + 1);
    }
    dp[0].update(0, 1);
    for(int i = 0; i < a.size(); i++) { // problems are here?
        auto it = lower_bound(ls[len[i] - 1].begin(), ls[len[i] - 1].end(), a[i]);
        int res = dp[len[i] - 1].query(it - ls[len[i] - 1].begin() - 1);
        auto it2 = lower_bound(ls[len[i]].begin(), ls[len[i]].end(), a[i]);
        dp[len[i]].update(it2 - ls[len[i]].begin(), res);
    }
    return {dp[LIS].query(ls[LIS].size() - 1), LIS};
}

void solve(istream &cin) {
    int n;
    cin >> n;
    vector<int> a(2*n - 1);
    for(int i = 0; i < n; i++) cin >> a[i];
//    for(int x: a) cout << x << ' ';
//    cout << endl;
    reverse(a.begin(), a.begin() + n);
    for(int i = n-2, curr = 0; i >= 0; i--, curr++) a[n + curr] = a[i];
//    for(int x: a) cout << x << ' ';
//    cout << endl;
    auto withStart = count_LIS(a);
    a.erase(a.begin() + a.size() / 2);
//    for(int x: a) cout << x << ' ';
//    cout << endl;
    auto withoutStart = count_LIS(a);
//    cout << endl;
    if(withStart.second == withoutStart.second) {
        withStart.first -= withoutStart.first;
    } else if(withStart.second > withoutStart.second){
        withoutStart.first = 0;
    } else {
        assert(false);
    }
    for(int i = 0; i < n - withStart.second; i++) {
        withStart.first *= 2;
        withStart.first %= MOD;
    }
    for(int i = 0; i < n - withoutStart.second - 1; i++) {
        withoutStart.first *= 2;
        withoutStart.first %= MOD;
    }
//    cout << withStart.first << ' ' << withoutStart.first << endl;
    cout << withStart.second << ' ' << (withStart.first + withoutStart.first) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ifstream in("1.in");
    solve(cin);
}

Compilation message (stderr)

zoltan.cpp: In member function 'void Fenwick::update(int, int)':
zoltan.cpp:14:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < f.size()) {
               ~~^~~~~~~~~~
zoltan.cpp: In function 'std::pair<int, int> count_LIS(std::vector<int>)':
zoltan.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) {
                    ~~^~~~~~~~~~
zoltan.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++)
                    ~~^~~~~~~~~~
zoltan.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i <= a.size(); i++) {
                    ~~^~~~~~~~~~~
zoltan.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i <= a.size(); i++) {
                    ~~^~~~~~~~~~~
zoltan.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) { // problems are here?
                    ~~^~~~~~~~~~

• Subtask 1: 21 / 140