Submission #1031360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031360		amine_aroua	Sequence (APIO23_sequence)	C++17	100 / 100	616 ms	47352 KiB

sequence

#include "sequence.h"
 
#include <bits/stdc++.h>
using namespace std;
pair<int ,int> comb(pair<int ,int> a , pair<int ,int> b)
{
    return {min(a.first , b.first) , max(a.second , b.second)};
}
struct segTree
{
    int BASE;
    vector<pair<int ,int>> tree;
    vector<int>  tag;
    void init(int n)
    {
        BASE = n;
        while(__builtin_popcount(BASE) != 1)
            BASE++;
        tag.assign(2*BASE , 0);
        tree.assign(2*BASE , {BASE , -BASE});
        for(int i = 0 ; i < n ; i++)
        {
            tree[i + BASE] = {i , i};
        }
        for(int i = BASE - 1 ; i >= 1 ; i--)
        {
            tree[i] = comb(tree[i<<1] , tree[i<<1|1]);
        }
    }
    void add(int node , int s , int e , int l , int r , int val)
    {
        if(s > r || l > e)
            return;
        if(l <= s && e <= r)
        {
            tree[node].first+=val;
            tree[node].second+=val;
            tag[node]+=val;
            return ;
        }
        int m = (s + e)>>1;
        add(node<<1 , s , m , l , r , val);
        add(node<<1|1 , m + 1 , e , l , r , val);
        tree[node] = comb(tree[node<<1] , tree[node<<1|1]);
        tree[node].first+=tag[node];
        tree[node].second+=tag[node];
    }
    void add(int l , int r , int val)
    {
        add(1 , 0 , BASE - 1  , l , r , val);
    }
     pair<int, int> query(int node ,int s , int e ,int l, int r) {
        if (l > e || s > r) {
            return {BASE , -BASE};
        }
        if (l <= s && e <= r) {
            return tree[node];
        }
        int mid = (s + e) >> 1;
        pair<int, int> res = comb(query(node << 1, s, mid, l, r) , query(node << 1|1, mid + 1, e, l, r));
        res.first += tag[node], res.second += tag[node];
        return res;
    }
    pair<int ,int> query(int l , int r)
    {
        return query(1 , 0 , BASE - 1 , l , r);
    }
    
}tree;
bool check(int i , int j , int w , int N)
{
    auto rt = tree.query(j + 1 , N);
    rt.first-=2*w;
    auto lt = tree.query(0, i);
    return (max(rt.first , lt.first) <= min(lt.second , rt.second));    
}
int sequence(int N, std::vector<int> A) 
{
    vector<int> occ[N];
    tree.init(N + 1);
    for(int i = 0 ; i < N ; i++)
    {
        A[i]--;
        occ[A[i]].push_back(i);
    }
    int ans = 1;

    for(int cur = 0 ; cur <N  ; cur++)
    {
        for(int i = 0 ; i < (int)occ[cur].size() ; i++)
        {
            tree.add(occ[cur][i] + 1 , N , -2);
        }
        for(int i = (int)occ[cur].size() - 1 ; i >= 0 ; i--)
        {
            tree.add(occ[cur][i] + 1 , N , 2);
            while(ans + i < (int)occ[cur].size() && (check(occ[cur][i] , occ[cur][ans + i] , ans + 1 , N)))
            {
                ans++;
            }
        }
        for(int i : occ[cur])
            tree.add(i + 1 , N , -2);
    }
    return ans;
}

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