Submission #763853

#TimeUsernameProblemLanguageResultExecution timeMemory
763853gg123_peSequence (APIO23_sequence)C++17
28 / 100
2083 ms8144 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...