Submission #1031334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031334		amine_aroua	Sequence (APIO23_sequence)	C++17	36 / 100	227 ms	45904 KiB

sequence

#include "sequence.h"
 
#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int sum , pfmax , pfmin;
};
Node comb(Node a , Node b)
{
    Node ans;
    ans.sum = a.sum + b.sum;
    ans.pfmax = max(a.sum + b.pfmax , a.pfmax);
    ans.pfmin = min(a.sum + b.pfmin , a.pfmin);
    return ans;
}
struct segTree
{
    int BASE;
    vector<Node> tree;
    void init(int n)
    {
        BASE = n;
        while(__builtin_popcount(BASE) != 1)
            BASE++;
        tree.assign(2*BASE , {0 , 0 , 0});
        for(int i = 0 ; i < n ; i++)
        {
            tree[i + BASE] = {-1 , 0 , -1};
        }
        for(int i = BASE - 1 ; i >= 1 ; i--)
        {
            tree[i] = comb(tree[i<<1] , tree[i<<1|1]);
        }
    }
    void upd(int i , int x)
    {
        tree[i + BASE] = {x , max(0 , x) , min(0 , x)};
        for(int j = (i + BASE) / 2 ; j >= 1 ; j>>=1)
        {
            tree[j] = comb(tree[j<<1] , tree[j<<1|1]);
        }
    }
    Node query(int l , int r)
    {
        if(l > r)
        {
            return {0 , 0 , 0};
        }
        l+=BASE;
        r+=BASE;
        if(l == r)
            return tree[l];
        Node lt = tree[l], rt = tree[r];
        while(l + 1 < r)
        {
            if(l%2 == 0)
            {
                lt = comb(lt , tree[l + 1]);
            }
            if(r%2 == 1)
            {
                rt = comb(tree[r - 1] , rt);
            }
            l>>=1;
            r>>=1;
        }
        return comb(lt , rt);
    }
}tree;
bool check(int i , int j , int i_ , int j_ , int w , int N)
{
    auto rt = tree.query(j , j_ - 1);
    int totj = tree.query(0 , j - 1).sum;
    int mxj = rt.pfmax + totj;
    int mnj = rt.pfmin + totj;
    auto lt = tree.query(i_+ 1 , i - 1);
    int toti = tree.query(0 , i_).sum;
    int mxi = lt.pfmax + toti;
    int mni = lt.pfmin + toti;
    int mx = mxj - mni;
    int mn = mnj - mxi;
    if(mn <= 0 && mx >= 0)
    {
        return 1;
    }
    else if(mn > 0)
    {
        if(w >= mn)
            return 1;
        return 0;
    }
    else
    {
        if(w >= abs(mx))
        {
            return 1;
        }
        return 0;
    }
    return 0;
}
int sequence(int N, std::vector<int> A) 
{
    vector<int> occ[N + 1];
    tree.init(N);
    for(int i = 0 ; i < N ; i++)
    {
        A[i]--;
        occ[A[i]].push_back(i);
    }
    int ans = 1;
    for(int cur = N - 1 ; cur >= 0 ; cur--)
    {
        for(int i = 0 ; i < (int)occ[cur + 1].size() ; i++)
        {
            tree.upd(occ[cur + 1][i], 1);
        }
        for(int i = 0 ; i < (int)occ[cur].size() ; i++)
        {
            tree.upd(occ[cur][i] , 0);
        }
        for(int i = (int)occ[cur].size() - 1 ; i >= 0 ; i--)
        {
            int j = (ans + i);
            int i_ = (i ? occ[cur][i - 1] : -1);
            int j_ = (j + 1 >= (int)occ[cur].size() ? N : occ[cur][j + 1]);
            while(ans + i < (int)occ[cur].size() && check(occ[cur][i] , occ[cur][ans + i] , i_ , j_ , ans + 1 , N))
            {
                ans++;
            }
        }
    }
    return ans;
}

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