제출 #763853

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

sequence

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

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 5e5 + 5; 

int n; 
int bit[N], c[N]; 

void upd(int x, int val){
    for(; x < N; x = (x|(x+1))) bit[x] += val; 
}
int sum(int x){
    int res = 0;
    for(; x >= 0; x = (x&(x+1)) - 1) res += bit[x];  
    return res; 
}
int get(int x){
    int l = 1, r = n; 
    while(l < r){
        int m = (l+r)>>1; 
        if(sum(m) >= x) r = m; 
        else l = m+1; 
    }
    return c[l]; 
}
int sequence(int Ni, vector<int> A) {
    n = Ni; 
    int ans = 1; 
    f(i,0,n){
        c[A[i]]++; 
        upd(A[i], 1); 

        f(j,i,n){
            int l = j - i + 1; 
            if(l&1){
                ans = max(ans, get((l+1)/2)); 
            }
            else{
                ans = max(ans, get(l/2)); 
                ans = max(ans, get(l/2 + 1)); 
            }
            if(j+1 < n) {
                c[A[j+1]]++; 
                upd(A[j+1], 1); 
            }
        }
        f(j,i,n){
            c[A[j]]--; 
            upd(A[j], -1); 
        }
    }
    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