제출 #751838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751838		1075508020060209tc	서열 (APIO23_sequence)	C++17	0 / 100	2044 ms	10312 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int lowbit(int x){return x&-x;}

struct BIT{
vector<int>bit;
int MX;
void init(int len){
for(int i=0;i<=len+100;i++){
    bit.push_back(0);
}
MX=len;
}
void upd(int pl,int vl){
while(pl<=MX){
    bit[pl]+=vl;
    pl+=lowbit(pl);
}
}
int qsum(int pl){
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}
int k_th(int k){

    int l=1;int r=MX;
    while(l<r){
        int mi=l+(r-l+1)/2;
        if(qsum(mi)<k){
            l=mi;
        }else{
            r=mi-1;
        }
    }
    return l+1;






int lg=__lg(MX);
int cnt=0;
int nw=0;
for(int i=lg;i>=0;i--){
    if(cnt+bit[nw+(1<<i)]<k){
        nw+=(1<<i);
        cnt+=bit[nw];
    }
}
return nw+1;
}
};


int n;
int ar[500005];
int freq[500005];

int slv(){
   int ans=0;
   BIT num;
   num.init((1<<(__lg(n)+1)));
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            freq[ar[r]]++;
            num.upd(ar[r],1);
            int len=r-l+1;
            ans=max(ans,freq[num.k_th((len+1)/2)]);
            ans=max(ans,freq[num.k_th((len+2)/2)]);
        }
        for(int r=1;r<=n;r++){
            freq[ar[r]]--;
            num.upd(ar[r],-1);
        }
    }
    return ans;
}


int sequence(int N, std::vector<int> A) {
    n=N;
    for(int i=0;i<n;i++){
        ar[i+1]=A[i];
    }
return slv();

  return 0;
}

/*

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
    }
    cout<<slv();


    return 0;
}

*/

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