Submission #936659

#TimeUsernameProblemLanguageResultExecution timeMemory
936659JuanJLSequence (APIO23_sequence)C++17
0 / 100
566 ms90776 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fst first #define snd second #define pb push_back #define forn(i,a,b) for(int i = a; i < b; i++) #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() #define mset(a,v) memset((a),(v),sizeof(a)) #define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n'; #define pi pair<int,int> #define pll pair<ll,ll> typedef long long ll; using namespace std; using namespace __gnu_pbds; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set; typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset; ll n; vector<ll> a; int sequence(int N, std::vector<int> A) { n=N; a.clear(); a.resize(n); forn(i,0,n) a[i]=A[i]; ll res = 0; /*if(n<=(2*pow(10,3))){ //Subtasks 1 , 2 cout<<n<<" "<<2*pow(10,3); cout<<"Tests 1 2"<<'\n'; forn(i,0,n){ indexed_multiset im; ll ocurr[n+1]; mset(ocurr,0); forn(j,i,n){ im.insert(a[j]); ocurr[a[j]]++; res = max(res,ocurr[*im.find_by_order((SZ(im)-1)/2)]); if(SZ(im)%2==0) res = max(res,ocurr[*im.find_by_order((SZ(im)-1)/2+1)]); } } }else{ cout<<"Tests 3\n";*/ vector<vector<ll>> p; set<ll> vals; map<ll,ll> cI; forn(i,0,n) vals.insert(a[i]); ll ind = 0; for(auto i:vals) cI[i]=ind,ind++; p.resize(SZ(cI)); forn(i,0,n) p[cI[a[i]]].pb(i); /*forn(i,0,n){ ll igu = SZ(p[cI[a[i]]]); ll men = p[cI[a[i]]][0]+(n-1)-p[cI[a[i]]][igu-1]; ll may = (p[cI[a[i]]][igu-1]-p[cI[a[i]]][0])-igu; if(may<=men+igu){ res=max(res,igu); }else{ ll preRes = 0; forn(j,0,SZ(p[cI[a[i]]])){ if(abs(p[cI[a[i]]][j]-p[cI[a[i]]][j-1])==1) preRes++; else break; } res=max(res,max(preRes,SZ(p[cI[a[i]]])-preRes)); } }*/ ll men = 0; ll may = 0; ll igu = 0; forn(i,0,SZ(p)){ men=0; may = 0; igu = 0; forn(j,0,SZ(p[i])){ if(abs(p[i][j]-p[i][j+1])==1) igu++; else break; } igu++; res=max(res,igu); res=max(res,SZ(p[i])-(igu)); may=(p[i][igu]-p[i][igu-1])-1; if(may<=men+igu) res = max(res,(ll)SZ(p[i])); //cout<<res<<" "<<i<<'\n'; } // } return res; }
#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...