oj.uz

Submission #199013

# Submission time Handle Problem Language Result Execution time Memory
199013 2020-01-28T16:20:14 Z dolphingarlic Zoltan (COCI16_zoltan) C++14
119 / 140
 275 ms 21360 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const ll MOD = 1e9 + 7;

int n, a[200001], g_len[200001];
ll pw[200001], g_num[200001];
vector<int> uniq;
pair<int, ll> lis[200001], lds[200001];
map<int, int> mp;

void update(int pos, int len, int num) {
    for (; pos <= n; pos += (pos & (-pos))) {
        if (g_len[pos] == len) {
            g_num[pos] = (g_num[pos] + num) % MOD;
        } else if (g_len[pos] < len) {
            g_len[pos] = len;
            g_num[pos] = num;
        }
    }
}
pair<int, int> query(int pos) {
    pair<int, ll> ans;
    for (; pos; pos -= (pos & (-pos))) {
        if (g_len[pos] == ans.first) {
            ans.second = (ans.second + g_num[pos]) % MOD;
        } else if (g_len[pos] > ans.first) {
            ans = {g_len[pos], g_num[pos]};
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    pw[0] = 1;
    FOR(i, 1, n + 1) {
        cin >> a[i];
        pw[i] = (pw[i - 1] << 1) % MOD;
        uniq.push_back(a[i]);
    }
    sort(uniq.begin(), uniq.end());
    uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());
    FOR(i, 0, uniq.size()) mp[uniq[i]] = i + 1;
    FOR(i, 1, n + 1) a[i] = mp[a[i]];
    FOR(i, 1, (n + 2) / 2) swap(a[i], a[n - i + 1]);

    FOR(i, 1, n + 1) {
        int len, num;
        tie(len, num) = query(a[i]);
        if (!len) num = 1;
        len++;
        lis[i] = {len, num};
        update(a[i] + 1, len, num);
    }
    FOR(i, 1, n + 1) a[i] = n - a[i] + 1, g_num[i] = g_len[i] = 0;
    FOR(i, 1, n + 1) {
        int len, num;
        tie(len, num) = query(a[i]);
        if (!len) num = 1;
        len++;
        lds[i] = {len, num};
        update(a[i] + 1, len, num);
    }

    int ans = -1;
    ll a_num = -1;
    FOR(i, 1, n + 1) {
        int len = lis[i].first + lds[i].first - 1;
        ll num = (pw[n - len] * (lis[i].second * lds[i].second) % MOD) % MOD;
        if (len == ans) {
            a_num = (a_num + num) % MOD;
        } else if (len > ans) {
            ans = len;
            a_num = num;
        }
    }
    cout << ans << ' ' << a_num;
    return 0;
}

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
zoltan.cpp:48:9:
     FOR(i, 0, uniq.size()) mp[uniq[i]] = i + 1;
         ~~~~~~~~~~~~~~~~~               
zoltan.cpp:48:5: note: in expansion of macro 'FOR'
     FOR(i, 0, uniq.size()) mp[uniq[i]] = i + 1;
     ^~~

Subtask #1
119.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 6 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 132 ms 17008 KB Output is correct
12 Correct 116 ms 14960 KB Output is correct
13 Correct 107 ms 14068 KB Output is correct
14 Incorrect 172 ms 14988 KB Output isn't correct
15 Incorrect 221 ms 18412 KB Output isn't correct
16 Incorrect 275 ms 21360 KB Output isn't correct
17 Correct 164 ms 19952 KB Output is correct
18 Correct 164 ms 19968 KB Output is correct
19 Correct 169 ms 19948 KB Output is correct
20 Correct 168 ms 20076 KB Output is correct