Submission #1033255

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033255	2024-07-24T15:17:10 Z	raphaelp	Zoltan (COCI16_zoltan)	C++14	21 / 140	342 ms	40428 KB

zoltan

#include <bits/stdc++.h>
using namespace std;
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);
        }
    }
    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;
        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++)
    {
        if (i == 0 || vals[i] != vals[i - 1])
            M[vals[i]] = buff++;
    }
    for (long long i = 0; i < N; i++)
        Tab[i] = M[Tab[i]];
    long long MOD = 1000000007;
    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	436 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	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	Incorrect	1 ms	604 KB	Output isn't correct
8	Incorrect	1 ms	604 KB	Output isn't correct
9	Incorrect	1 ms	604 KB	Output isn't correct
10	Incorrect	1 ms	604 KB	Output isn't correct
11	Runtime error	210 ms	35280 KB	Memory limit exceeded
12	Runtime error	188 ms	32852 KB	Memory limit exceeded
13	Incorrect	162 ms	23696 KB	Output isn't correct
14	Runtime error	225 ms	33120 KB	Memory limit exceeded
15	Runtime error	319 ms	37200 KB	Memory limit exceeded
16	Runtime error	342 ms	40428 KB	Memory limit exceeded
17	Runtime error	265 ms	37968 KB	Memory limit exceeded
18	Runtime error	249 ms	37840 KB	Memory limit exceeded
19	Runtime error	266 ms	37864 KB	Memory limit exceeded
20	Runtime error	241 ms	37856 KB	Memory limit exceeded