Submission #1033357

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033357	2024-07-24T17:13:51 Z	raphaelp	Zoltan (COCI16_zoltan)	C++14	21 / 140	331 ms	40272 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)
            temp2.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

21.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	348 KB	Output isn't correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Incorrect	0 ms	348 KB	Output isn't 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	Incorrect	1 ms	604 KB	Output isn't correct
8	Incorrect	1 ms	604 KB	Output isn't correct
9	Incorrect	1 ms	600 KB	Output isn't correct
10	Incorrect	1 ms	604 KB	Output isn't correct
11	Runtime error	196 ms	35280 KB	Memory limit exceeded
12	Runtime error	179 ms	33108 KB	Memory limit exceeded
13	Incorrect	165 ms	23812 KB	Output isn't correct
14	Runtime error	209 ms	33104 KB	Memory limit exceeded
15	Runtime error	331 ms	37260 KB	Memory limit exceeded
16	Runtime error	319 ms	40272 KB	Memory limit exceeded
17	Runtime error	257 ms	38224 KB	Memory limit exceeded
18	Runtime error	246 ms	37972 KB	Memory limit exceeded
19	Runtime error	269 ms	37836 KB	Memory limit exceeded
20	Runtime error	264 ms	38224 KB	Memory limit exceeded