Submission #1182067

#TimeUsernameProblemLanguageResultExecution timeMemory
1182067cpdreamerSequence (APIO23_sequence)C++20
28 / 100
2096 ms120440 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define P pair #define F first #define all(v) v.begin(),v.end() #define V vector #define pb push_back #define S second const ll MOD=(ll)1e9+7; void file() { freopen("input.txt.txt", "r", stdin); freopen("output.txt.txt", "w", stdout); } struct segtree{ private: struct node{ int mind; int maxd; }; node single(int v){ return {v,v}; } node neutral={INT_MAX,INT_MIN}; node merge(node a,node b){ return {min(a.mind,b.mind),max(a.maxd,b.maxd)}; } node modification(node a,int v){ return {a.mind+v,a.maxd+v}; } int operation_modifier(int a,int v){ return a+v; } public: int size; V<node>query; V<int>operation; void init(int n){ size=1; while(size<n)size*=2; query.assign(2*size,neutral); operation.assign(2 * size, 0); } void build(V<int>a,int x,int lx,int rx){ if(rx-lx==1){ if(lx<(int)a.size()){ query[x]=single(a[lx]); } return; } int m=(lx+rx)/2; build(a,2*x+1,lx,m); build(a,2*x+2,m,rx); query[x]=merge(query[2*x+1],query[2*x+2]); } void build(V<int>a){ build(a,0,0,size); } void set(int l,int r,int v,int x,int lx,int rx){ if(lx>=r || rx<=l){ return; } if(l<=lx && rx<=r){ query[x]=modification(query[x],v); operation[x]= operation_modifier(operation[x],v); return; } int m=(lx+rx)/2; set(l,r,v,2*x+1,lx,m); set(l,r,v,2*x+2,m,rx); query[x]=modification(merge(query[2*x+1],query[2*x+2]),operation[x]); } void set(int l,int r,int v){ set(l,r,v,0,0,size); } node calc(int l,int r,int x,int lx,int rx){ if(rx<=l || lx>=r){ return neutral; } if(l<=lx && rx<=r) return query[x]; int m=(lx+rx)/2; node a=calc(l,r,2*x+1,lx,m); node b=calc(l,r,2*x+2,m,rx); return modification(merge(a,b),operation[x]); } int mind(int l,int r){ return calc(l,r,0,0,size).mind; } int maxd(int l,int r){ return calc(l,r,0,0,size).maxd; } }; bool inter(P<int,int>a,P<int,int>b){ if(a.F>b.F) swap(a,b); return a.S>=b.F; } int f(int N,V<int>A){ V<int>a(N+1); V<int>occ(N+1); V<V<int>>pos(N+1); set<int>st; for(int i=1;i<=N;i++) { a[i] = A[i - 1]; occ[a[i]]++; pos[a[i]].pb(i); st.insert(a[i]); } V<int>d; for(auto u:st) d.pb(u); V<int>b=a; sort(all(b)); int ans=max(occ[b[(N+1)/2]],occ[b[(N+2)/2]]); int l=1,r=N; while(l<=r){ int m=l+(r-l)/2; V<int>vp(N+1); vp[0]=0; for(int i=1;i<=N;i++){ vp[i]=vp[i-1]+1; } segtree tree; tree.init(N); tree.build(vp); bool flag=false; for(auto u:d){ int sz=(int)pos[u].size(); for(int i=0;i+m-1<sz;i++){ int x=pos[u][i]; int y=pos[u][i+m-1]; P<int,int>p1={tree.mind(0,x+1),tree.maxd(0,x+1)}; P<int,int>p2={tree.mind(y,N+1),tree.maxd(y,N+1)}; if(inter(p1,p2)){ flag=true; } } for(int i=0;i<sz;i++){ tree.set(pos[u][i],N+1,-2); } for(int i=0;i+m-1<sz;i++){ int x=pos[u][i]; int y=pos[u][i+m-1]; P<int,int>p1={tree.mind(0,x+1),tree.maxd(0,x+1)}; P<int,int>p2={tree.mind(y,N+1),tree.maxd(y,N+1)}; if(inter(p1,p2)){ flag=true; } } } if(flag){ ans=max(ans,m); l=m+1; } else r=m-1; } return ans; } int sequence(int N, std::vector<int> A) { int ans=f(N,A); return ans; } void solve() { int n; cin>>n; V<int>A(n); for(int i=0;i<n;i++){ cin>>A[i]; } cout<<sequence(n,A)<<endl; }

Compilation message (stderr)

sequence.cpp: In function 'void file()':
sequence.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("input.txt.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("output.txt.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...