Submission #97912

#	Time	Username	Problem	Language	Result	Execution time	Memory
97912		szawinis	Zoltan (COCI16_zoltan)	C++17	77 / 140	240 ms	33792 KiB

zoltan

#include <bits/stdc++.h>
#define long long long
using namespace std;
const long MOD = 1e9+7;

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

pair<long, int> count_LIS(vector<int> a) {
    vector<vector<int> > ls(a.size() + 1);
    vector<int> f, len(a.size());
    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;
//        cout << a[i] << ' ' << len[i] << endl;
    }
//    cout << endl;
    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 < ls.size(); i++) {
        sort(ls[i].begin(), ls[i].end());
        ls[i].resize(unique(ls[i].begin(), ls[i].end()) - ls[i].begin());
    }
    vector<Fenwick> dp;
    for(int i = 0; i < ls.size(); i++) {
        dp.push_back(Fenwick(ls[i].size()));
    }
    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]);
        long 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);
//        cout << i << ' ' << it - ls[len[i] - 1].begin() << ' ' << it2 - ls[len[i]].begin() << ' ' << res << endl;
    }
//    cout << ls[LIS].size() << endl;
    return {dp[LIS].query(ls[LIS].size() - 1), LIS};
}

void solve(istream &cin) {
    int n;
    cin >> n;
    vector<int> a(n), b0, b1;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = n-1; i > 0; i--) b0.push_back(a[i]);
    for(int i = 1; i < n; i++) b0.push_back(a[i]);
    for(int i = n-1; i >= 0; i--) b1.push_back(a[i]);
    for(int i = 1; i < n; i++) b1.push_back(a[i]);
    auto withoutStart = count_LIS(b0);
//    cout << endl;
    auto withStart = count_LIS(b1);
    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("2.in");
    solve(cin);
}

Compilation message (stderr)

zoltan.cpp: In member function 'void Fenwick::update(int, long long int)':
zoltan.cpp:13:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < f.size()) {
               ~~^~~~~~~~~~
zoltan.cpp: In function 'std::pair<long long int, int> count_LIS(std::vector<int>)':
zoltan.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) {
                    ~~^~~~~~~~~~
zoltan.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++)
                    ~~^~~~~~~~~~
zoltan.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ls.size(); i++) {
                    ~~^~~~~~~~~~~
zoltan.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ls.size(); i++) {
                    ~~^~~~~~~~~~~
zoltan.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) { // problems are here?
                    ~~^~~~~~~~~~

• Subtask 1: 77 / 140