oj.uz

답안 #199028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199028 2020-01-28T17:06:47 Z dolphingarlic Zoltan (COCI16_zoltan) C++14
119 / 140
 268 ms 21512 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, ll 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, ll> 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] * 2) % 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]];
    reverse(a + 1, a + n + 1);

    FOR(i, 1, n + 1) {
        int len;
        ll num;
        tie(len, num) = query(a[i]);
        if (!len) num = 1;
        len++;
        lis[i] = {len, num};
        update(a[i] + 1, len, num);
    }
    FOR(i, 0, n + 1) a[i] = n - a[i], g_num[i] = g_len[i] = 0;
    FOR(i, 1, n + 1) {
        int len;
        ll 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

# 결과 실행 시간 메모리 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 7 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 6 ms 504 KB Output is correct
11 Correct 132 ms 17008 KB Output is correct
12 Correct 114 ms 14828 KB Output is correct
13 Correct 106 ms 14068 KB Output is correct
14 Incorrect 166 ms 15060 KB Output isn't correct
15 Incorrect 220 ms 18412 KB Output isn't correct
16 Incorrect 268 ms 21512 KB Output isn't correct
17 Correct 171 ms 20040 KB Output is correct
18 Correct 161 ms 19952 KB Output is correct
19 Correct 166 ms 19948 KB Output is correct
20 Correct 165 ms 19944 KB Output is correct