oj.uz

Submission #97944

# Submission time Handle Problem Language Result Execution time Memory
97944 2019-02-19T15:08:19 Z szawinis Zoltan (COCI16_zoltan) C++17
140 / 140
 360 ms 18036 KB 
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int N = 2e5+1;

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

int len[2*N], pre[2*N], curr[2*N];
vector<int> a, f, dp[N];

pair<int, int> count_LIS() {
    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;
        assert(len[i] < N);
        LIS = max(len[i], LIS);
        if(it == f.end())
            f.push_back(x);
        else
            *it = x;
    }
    f.clear();

    dp[0].push_back(0);
    for(int i = 0; i < a.size(); i++)
        dp[len[i]].push_back(a[i]);
    for(int i = 0; i <= LIS; i++) {
        sort(dp[i].begin(), dp[i].end());
        dp[i].resize(unique(dp[i].begin(), dp[i].end()) - dp[i].begin());
    }
    for(int i = 0; i < a.size(); i++) {
        auto it = lower_bound(dp[len[i] - 1].begin(), dp[len[i] - 1].end(), a[i]);
        pre[i] = it - dp[len[i] - 1].begin() - 1;
        auto it2 = lower_bound(dp[len[i]].begin(), dp[len[i]].end(), a[i]);
        curr[i] = it2 - dp[len[i]].begin();
    }

    for(int i = 0; i <= LIS; i++) {
        dp[i].assign(dp[i].size() + 2, 0);
    }
    update(dp[0], 0, 1);
    for(int i = 0; i < a.size(); i++) { // problems are here?
        int res = query(dp[len[i] - 1], pre[i]);
        update(dp[len[i]], curr[i], res);
    }
    return {query(dp[LIS], dp[LIS].size() - 2), LIS};
}

void solve(istream &cin) {
    int n;
    cin >> n;
    a.resize(2*n - 1);
    for(int i = 0; i < n; i++) cin >> a[i];
    reverse(a.begin(), a.begin() + n);
    for(int i = n-2, curr = 0; i >= 0; i--, curr++) a[n + curr] = a[i];
    auto withStart = count_LIS();
    a.erase(a.begin() + a.size() / 2);
    auto withoutStart = count_LIS();
    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.second << ' ' << (withStart.first + withoutStart.first) % MOD;
}

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

Compilation message

zoltan.cpp: In function 'void update(std::vector<int>&, int, int)':
zoltan.cpp:8:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i < f.size()) {
           ~~^~~~~~~~~~
zoltan.cpp: In function 'std::pair<int, int> count_LIS()':
zoltan.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) {
                    ~~^~~~~~~~~~
zoltan.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++)
                    ~~^~~~~~~~~~
zoltan.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) {
                    ~~^~~~~~~~~~
zoltan.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) { // problems are here?
                    ~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 5056 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 9 ms 5092 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 9 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct
11 Correct 203 ms 15312 KB Output is correct
12 Correct 149 ms 14068 KB Output is correct
13 Correct 148 ms 13424 KB Output is correct
14 Correct 213 ms 12820 KB Output is correct
15 Correct 297 ms 14200 KB Output is correct
16 Correct 320 ms 15456 KB Output is correct
17 Correct 360 ms 18036 KB Output is correct
18 Correct 346 ms 17816 KB Output is correct
19 Correct 357 ms 17804 KB Output is correct
20 Correct 311 ms 17752 KB Output is correct