Submission #1033392

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033392	2024-07-24T17:57:08 Z	raphaelp	Zoltan (COCI16_zoltan)	C++14	112 / 140	309 ms	13904 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;
                count[x] = count[x] % MOD;
            }
        }
        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 = (long long)(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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 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	206 ms	13192 KB	Output is correct
12	Correct	174 ms	12004 KB	Output is correct
13	Correct	167 ms	8372 KB	Output is correct
14	Incorrect	204 ms	11856 KB	Output isn't correct
15	Incorrect	309 ms	13904 KB	Output isn't correct
16	Incorrect	306 ms	13204 KB	Output isn't correct
17	Correct	256 ms	13904 KB	Output is correct
18	Correct	252 ms	13764 KB	Output is correct
19	Correct	235 ms	13904 KB	Output is correct
20	Correct	244 ms	13904 KB	Output is correct