Submission #1168650

#TimeUsernameProblemLanguageResultExecution timeMemory
1168650rayan_bdSequence (APIO23_sequence)C++20
0 / 100
687 ms148368 KiB
#include <bits/stdc++.h> using namespace std; const double INF = 5e18; const int mxN = 5e5+100; #define fi first #define se second #define all(v) v.begin(), v.end() vector<int> seg[mxN*4]; vector<int> ar; void build(int node,int start,int end){ if(start==end){ seg[node]={ar[start]}; return; } int mid=start+(end-start)/2; build(node*2+1,start,mid); build(node*2+2,mid+1,end); merge(all(seg[node*2+1]),all(seg[node*2+2]),back_inserter(seg[node])); } int qry(int node,int start,int end,int l,int r,int k){ if(start>r||end<l) return 0; if(start>=l&&end<=r) return upper_bound(all(seg[node]),k)-seg[node].begin(); int mid=start+(end-start)/2; return qry(node*2+1,start,mid,l,r,k)+qry(node*2+2,mid+1,end,l,r,k); } int sequence(int N,vector<int> A){ ar=A; for(int i=0;i<N*4+100;++i) seg[i].clear(); build(0,0,N-1); map<int,pair<int,int>> mp; for(int i=0;i<N;++i){ if(!mp.count(A[i])) mp[A[i]].fi=i; mp[A[i]].se=i; } int ans=1; for(auto it:A){ int len=(mp[it].se-mp[it].fi+1); if(len==1) continue; if(len<=4) ans=2; if(len>=5){ int pos=qry(0,0,N-1,mp[it].fi+1,mp[it].se-1,it)+1; if(len&1^1){ if(pos==((len+1)/2)) ans=2; if(pos==((len+1)/2+1)) ans=2; ++pos; if(pos==(len+1)/2) ans=2; if(pos==((len+1)/2+1)) ans=2; }else{ if(pos==(len+1)/2) ans=2; else if(pos+1==(len+1)/2) ans=2; } } } 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...