Submission #1030958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030958		amine_aroua	Sequence (APIO23_sequence)	C++17	12 / 100	116 ms	17624 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>
using namespace std;
int mid(vector<int> A)
{
    sort(A.begin() , A.end());
    return A[((int)A.size() - 1)/2];
}
struct segTree
{
    int BASE;
    vector<int> tree;
    segTree(int n)
    {
        BASE = 2*n + 1;
        while(__builtin_popcount(BASE) != 1)
            BASE++;
        tree.assign(2*BASE , BASE);
    }
    void upd(int i , int x)
    {
        if(tree[i + BASE] <= x)
            return;
        tree[i + BASE] = x;
        for(int j = (i + BASE) / 2 ; j >= 1 ; j>>=1)
        {
            tree[j] = min(tree[j<<1] , tree[j<<1|1]);
        }
    }
    int query(int l , int r)
    {
        l+=BASE;
        r+=BASE;
        if(l == r)
            return tree[l];
        int mn = min(tree[l] , tree[r]);
        while(l + 1 < r)
        {
            if(l%2 == 0)
            {
                mn = min(mn , tree[l + 1]);
            }
            if(r%2 == 1)
            {
                mn = min(mn , tree[r - 1]);
            }
            l>>=1;
            r>>=1;
        }
        return mn;
    }
};
int getMax(int N , vector<int> A)
{
    segTree tree(N);
    tree.upd(0 + N, 0);
    int ans = 0;
    for(int i = 1 ; i <= N ; i++)
    {
        int mn = tree.query(0 , A[i] + N);
        ans = max(ans , (i + A[i] - mn)/2);
        tree.upd(A[i] + N , i + A[i]);
    }
    return ans;
}
int sequence(int N, std::vector<int> A) 
{
    int m = mid(A);
    if(m != 2)
    {
        return count(A.begin() , A.end() , m);
    }
    int mx = count(A.begin() , A.end() , m);
    vector<int> pref(N + 1);
    for(int i = 0 ; i < N ; i++)
    {
        pref[i + 1] = (A[i] == 1 ? 1 : -1) + pref[i];
    }
    mx = max(mx , getMax(N , pref));
    pref = vector<int>(N + 1);
    for(int i = 0 ; i < N ; i++)
    {
        pref[i + 1] = (A[i] == 3 ? 1 : -1) + pref[i];
    }
    mx = max(mx , getMax(N , pref));
    return mx;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 12 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18