제출 #289165

#제출 시각아이디문제언어결과실행 시간메모리
289165TadijaSebezFibonacci representations (CEOI18_fib)C++11
50 / 100
4072 ms135716 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> const int mod=1e9+7; const int inf=1e9+1000; int add(int x,int y){x+=y;return x>=mod?x-mod:x;} int mul(int x,int y){return (ll)x*y%mod;} #define matrix vector<vector<int>> matrix operator * (matrix a,matrix b){ matrix ans(2,vector<int>(2,0)); for(int i=0;i<2;++i) for(int j=0;j<2;++j) for(int k=0;k<2;++k) ans[i][j]=add(ans[i][j],mul(a[i][k],b[k][j])); return ans; } matrix pow(matrix x,int k){ matrix ans(2,vector<int>(2,0)); ans[0][0]=ans[1][1]=1; for(;k;k>>=1,x=x*x)if(k&1)ans=ans*x; return ans; } matrix build(int sz){ return {{1,1},{(sz-1)/2,sz/2}}; } const int N=100050; matrix po[N]; int root; matrix idx; mt19937 rng(time(0)); namespace Treap{ const int M=N*20; int ls[M],rs[M],tsz,pri[M]; pii key[M]; matrix sum[M],my[M]; void pull(int c){sum[c]=sum[rs[c]]*my[c]*sum[ls[c]];} int Make(pii a,matrix x){tsz++;assert(tsz<M);my[tsz]=sum[tsz]=x;key[tsz]=a;pri[tsz]=rng();return tsz;} void rot_l(int&c){int a=rs[c],b=ls[a];rs[c]=b;ls[a]=c;pull(c);pull(a);c=a;} void rot_r(int&c){int a=ls[c],b=rs[a];ls[c]=b;rs[a]=c;pull(c);pull(a);c=a;} void Ins(int&c,pii a,matrix x){ if(!c)c=Make(a,x); else if(key[c]==a)my[c]=x,pull(c); else if(key[c]<a){ Ins(rs[c],a,x); if(pri[rs[c]]>pri[c])rot_l(c); else pull(c); }else{ Ins(ls[c],a,x); if(pri[ls[c]]>pri[c])rot_r(c); else pull(c); } } } matrix make(pii p,int dist){ return po[(p.second-p.first)/2-1]*build(dist); } set<pii> seg; void Ins(pii p){ seg.insert(p); auto it=seg.find(p); if(it==seg.begin())Treap::Ins(root,p,make(p,p.first+1)); else Treap::Ins(root,p,make(p,p.first+1-(prev(it)->second-1))); if(next(it)!=seg.end())Treap::Ins(root,*next(it),make(*next(it),next(it)->first+1-(p.second-1))); } void Rem(pii p){ auto it=seg.find(p); int l=0; if(it!=seg.begin())l=prev(it)->second-1; Treap::Ins(root,p,idx); if(next(it)!=seg.end())Treap::Ins(root,*next(it),make(*next(it),next(it)->first+1-l)); seg.erase(it); } void Add(int x){ auto it=seg.upper_bound({x,inf}); if(it==seg.begin()||prev(it)->second<x){ int l=x-1,r=x+1; if(it!=seg.begin()&&prev(it)->second==x-1)l=prev(it)->first,Rem(*prev(it)); if(it!=seg.end()&&it->first==x+1)r=it->second,Rem(*it); Ins({l,r}); }else{ it--; if(x%2==it->first%2){ int l,r;tie(l,r)=*it; Rem(*it); if(l<min(x,r-2))Ins({l,min(x,r-2)}); Add(r+(x==r)); }else{ int l,r;tie(l,r)=*it; Rem(*it); if(l+1<x)Ins({l+1,x}); if(l>0)Add(max(1,l-1)); Add(r); } } } int Solve(){ matrix m=Treap::sum[root]; return add(m[0][0],m[1][0]); } int main(){ idx={{1,0},{0,1}}; Treap::sum[0]=idx; po[0]=idx; po[1]=build(2); for(int i=2;i<N;i++)po[i]=po[i-1]*po[1]; int n; scanf("%i",&n); for(int i=1;i<=n;i++){ int a; scanf("%i",&a); Add(a); printf("%i\n",Solve()); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

fib.cpp: In function 'int main()':
fib.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
fib.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |   scanf("%i",&a);
      |   ~~~~~^~~~~~~~~
#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...