제출 #752207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
752207		aryan12	서열 (APIO23_sequence)	C++17	28 / 100	2070 ms	8288 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
int seg[N * 4];

void Build(int l, int r, int pos)
{
    seg[pos] = 0;
    if(l == r) return;
    int mid = (l + r) / 2;
    Build(l, mid, pos * 2);
    Build(mid + 1, r, pos * 2 + 1);
}

void Update(int l, int r, int pos, int qpos, int qval)
{
    seg[pos] += qval;
    if(l == r) return;
    int mid = (l + r) / 2;
    if(qpos <= mid)
    {
        Update(l, mid, pos * 2, qpos, qval);
    }
    else
    {
        Update(mid + 1, r, pos * 2 + 1, qpos, qval);
    }
}

int Query(int l, int r, int pos, int qval)
{
    if(l == r)
    {
        return seg[pos];
    }
    int mid = (l + r) / 2;
    if(seg[pos * 2] >= qval)
    {
        return Query(l, mid, pos * 2, qval);
    }
    else
    {
        return Query(mid + 1, r, pos * 2 + 1, qval - seg[pos * 2]);
    }
}

int sequence(int n, vector<int> a) 
{
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        Build(1, n, 1);
        for(int j = i; j < n; j++)
        {
            Update(1, n, 1, a[j], 1);
            int len = j - i + 1;
            int median = (len + 1) / 2;
            ans = max(ans, Query(1, n, 1, median));
            median = (len + 2) / 2;
            ans = max(ans, Query(1, n, 1, median));
        }
    }
    return ans;
}

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