제출 #97913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97913		szawinis	Zoltan (COCI16_zoltan)	C++17	91 / 140	236 ms	33792 KiB

zoltan

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

struct Fenwick {
    vector<int> f;
    Fenwick() {}
    Fenwick(int n) {
        f = vector<int>(n+2);
    }
    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;
    }
};

pair<int, 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(ls.size());
    for(int i = 0; i < ls.size(); i++) {
        dp[i] = 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]);
        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);
//        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;
    b0.reserve(2*n);
    b1.reserve(2*n);
    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);
}

컴파일 시 표준 에러 (stderr) 메시지

zoltan.cpp: In member function 'void Fenwick::update(int, 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<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: 91 / 140