Submission #1033389

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033389	2024-07-24T17:55:35 Z	raphaelp	Zoltan (COCI16_zoltan)	C++14	112 / 140	309 ms	15440 KB

zoltan

#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

#	Verdict	Execution time	Memory	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