Submission #1033374

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033374	2024-07-24T17:24:19 Z	raphaelp	Zoltan (COCI16_zoltan)	C++14	77 / 140	372 ms	40524 KB

zoltan

#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000007;
class SegTree
{
private:
    vector<long long> st, count;
    long long N;
    long long l(long long x) { return (x << 1); }
    long long r(long long x) { return (x << 1) + 1; }
    void update(long long L, long long R, long long a, long long val, long long c, long long 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
        {
            long long 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<long long, long long> RSQ(long long L, long long R, long long a, long long b, long long x)
    {
        if (L > b || R < a)
            return {0, 0};
        if (L >= a && R <= b)
            return {st[x], count[x]};
        long long m = (L + R) / 2;
        pair<long long, long long> 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(long long x)
    {
        N = pow(2, ceil(log2(x)));
        st.assign(2 * N, 0);
        count.assign(2 * N, 0);
    }
    void update(long long x, long long val, long long c) { update(0, N - 1, x, val, c, 1); }
    pair<long long, long long> RSQ(long long a, long long b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
    long long N;
    cin >> N;
    vector<long long> Tab(N), vals(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> Tab[i];
        vals[i] = Tab[i];
    }
    sort(vals.begin(), vals.end());
    map<long long, long long> M;
    long long buff = 1;
    for (long long i = 0; i < N; i++)
    {
        M[vals[i]] = buff++;
    }
    for (long long i = 0; i < N; i++)
        Tab[i] = M[Tab[i]];
    vector<pair<long long, long long>> ansleft(N), ansright(N);
    SegTree STL(N + 1), STR(N + 1);
    long long best = 0;
    for (long long 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 (long long i = 0; i < N; i++)
    {
        if (ansright[i].first + ansleft[i].first == best)
            tot = (tot + (ansright[i].second * ansleft[i].second)) % MOD;
    }
    for (long long i = 0; i < N - best + 1; i++)
    {
        tot = (tot * 2) % MOD;
    }
    cout << best - 1 << ' ' << tot;
}

Subtask #1

77.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 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	2 ms	612 KB	Output is correct
8	Correct	2 ms	600 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Runtime error	235 ms	35144 KB	Memory limit exceeded
12	Runtime error	191 ms	32848 KB	Memory limit exceeded
13	Correct	203 ms	23636 KB	Output is correct
14	Runtime error	235 ms	33108 KB	Memory limit exceeded
15	Runtime error	319 ms	37200 KB	Memory limit exceeded
16	Runtime error	372 ms	40524 KB	Memory limit exceeded
17	Runtime error	268 ms	37968 KB	Memory limit exceeded
18	Runtime error	306 ms	37844 KB	Memory limit exceeded
19	Runtime error	264 ms	37968 KB	Memory limit exceeded
20	Runtime error	267 ms	37788 KB	Memory limit exceeded