oj.uz

답안 #1033389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033389 2024-07-24T17:55:35 Z raphaelp Zoltan (COCI16_zoltan) C++14
112 / 140
 309 ms 15440 KB 
#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000007;
class SegTree
{
private:
    vector<int> st, count;
    int N;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void update(int L, int R, int a, int val, int c, int x)
    {
        if (L > a || R < a)
            return;
        if (L == a && R == a)
        {
            if (val > st[x])
            {
                st[x] = val;
                count[x] = 0;
            }
            if (val == st[x])
                count[x] += c;
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, val, c, l(x));
            update(m + 1, R, a, val, c, r(x));
            st[x] = max(st[l(x)], st[r(x)]);
            count[x] = ((st[l(x)] == st[x]) ? count[l(x)] : 0) + ((st[r(x)] == st[x]) ? count[r(x)] : 0);
            count[x] = count[x] % MOD;
        }
    }
    pair<int, int> RSQ(int L, int R, int a, int b, int x)
    {
        if (L > b || R < a)
            return {0, 0};
        if (L >= a && R <= b)
            return {st[x], count[x]};
        int m = (L + R) / 2;
        pair<int, int> temp1 = RSQ(L, m, a, b, l(x)), temp2 = RSQ(m + 1, R, a, b, r(x));
        if (temp1.first < temp2.first)
            swap(temp1, temp2);
        if (temp1.first == temp2.first)
            temp1.second += temp2.second;
        temp1.second = temp1.second % MOD;
        return temp1;
    }

public:
    SegTree(int x)
    {
        N = pow(2, ceil(log2(x)));
        st.assign(2 * N, 0);
        count.assign(2 * N, 0);
    }
    void update(int x, int val, int c) { update(0, N - 1, x, val, c, 1); }
    pair<int, int> RSQ(int a, int b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
    int N;
    cin >> N;
    vector<int> Tab(N), vals(N);
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
        vals[i] = Tab[i];
    }
    sort(vals.begin(), vals.end());
    map<int, int> M;
    int buff = 1;
    for (int i = 0; i < N; i++)
    {
        M[vals[i]] = buff++;
    }
    for (int i = 0; i < N; i++)
        Tab[i] = M[Tab[i]];
    M.clear();
    vals.clear();
    vector<pair<int, int>> ansleft(N), ansright(N);
    SegTree STL(N + 1), STR(N + 1);
    int best = 0;
    for (int i = N - 1; i >= 0; i--)
    {
        ansleft[i] = STL.RSQ(0, Tab[i] - 1);
        ansright[i] = STR.RSQ(Tab[i] + 1, N);
        ansleft[i].first++, ansright[i].first++;
        if (ansleft[i].first == 1)
            ansleft[i].second++;
        if (ansright[i].first == 1)
            ansright[i].second++;
        ansleft[i].second = ansleft[i].second % MOD;
        ansright[i].second = ansright[i].second % MOD;
        STL.update(Tab[i], ansleft[i].first, ansleft[i].second);
        STR.update(Tab[i], ansright[i].first, ansright[i].second);
        best = max(best, ansright[i].first + ansleft[i].first);
    }
    long long tot = 0;
    for (int i = 0; i < N; i++)
    {
        if (ansright[i].first + ansleft[i].first == best)
            tot = (tot + (long long)(ansright[i].second * ansleft[i].second)) % MOD;
    }
    for (int i = 0; i < N - best + 1; i++)
    {
        tot = (tot * 2) % MOD;
    }
    cout << best - 1 << ' ' << tot;
}

Subtask #1
112.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 432 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 196 ms 14320 KB Output is correct
12 Correct 156 ms 13080 KB Output is correct
13 Correct 152 ms 9500 KB Output is correct
14 Incorrect 232 ms 13224 KB Output isn't correct
15 Incorrect 236 ms 15440 KB Output isn't correct
16 Incorrect 309 ms 15188 KB Output isn't correct
17 Correct 241 ms 15188 KB Output is correct
18 Correct 255 ms 15188 KB Output is correct
19 Correct 242 ms 15184 KB Output is correct
20 Correct 235 ms 15188 KB Output is correct