oj.uz

Submission #289164

# Submission time Handle Problem Language Result Execution time Memory
289164 2020-09-02T12:22:17 Z TadijaSebez Fibonacci representations (CEOI18_fib) C++11
50 / 100
 4000 ms 89208 KB 
#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*10;
	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;
}

Compilation message

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);
      |   ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 62200 KB Output is correct
2 Correct 81 ms 62200 KB Output is correct
3 Correct 81 ms 62200 KB Output is correct
4 Correct 81 ms 62200 KB Output is correct
5 Correct 80 ms 62200 KB Output is correct
6 Correct 83 ms 62200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 62200 KB Output is correct
2 Correct 81 ms 62200 KB Output is correct
3 Correct 81 ms 62200 KB Output is correct
4 Correct 81 ms 62200 KB Output is correct
5 Correct 80 ms 62200 KB Output is correct
6 Correct 83 ms 62200 KB Output is correct
7 Correct 82 ms 62200 KB Output is correct
8 Correct 82 ms 62200 KB Output is correct
9 Correct 82 ms 62204 KB Output is correct
10 Correct 86 ms 62332 KB Output is correct
11 Correct 84 ms 62200 KB Output is correct
12 Correct 82 ms 62200 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 62280 KB Output is correct
2 Correct 81 ms 62200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 62200 KB Output is correct
2 Correct 81 ms 62200 KB Output is correct
3 Correct 81 ms 62200 KB Output is correct
4 Correct 81 ms 62200 KB Output is correct
5 Correct 80 ms 62200 KB Output is correct
6 Correct 83 ms 62200 KB Output is correct
7 Correct 82 ms 62200 KB Output is correct
8 Correct 82 ms 62200 KB Output is correct
9 Correct 82 ms 62204 KB Output is correct
10 Correct 86 ms 62332 KB Output is correct
11 Correct 84 ms 62200 KB Output is correct
12 Correct 82 ms 62200 KB Output is correct
13 Correct 84 ms 62280 KB Output is correct
14 Correct 81 ms 62200 KB Output is correct
15 Correct 80 ms 62200 KB Output is correct
16 Correct 85 ms 62200 KB Output is correct
17 Correct 82 ms 62204 KB Output is correct
18 Correct 84 ms 62200 KB Output is correct
19 Correct 82 ms 62284 KB Output is correct
20 Correct 85 ms 62444 KB Output is correct
21 Correct 88 ms 62200 KB Output is correct
22 Correct 89 ms 62200 KB Output is correct
23 Correct 86 ms 62200 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 62200 KB Output is correct
2 Execution timed out 4102 ms 89208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 62200 KB Output is correct
2 Correct 81 ms 62200 KB Output is correct
3 Correct 81 ms 62200 KB Output is correct
4 Correct 81 ms 62200 KB Output is correct
5 Correct 80 ms 62200 KB Output is correct
6 Correct 83 ms 62200 KB Output is correct
7 Correct 82 ms 62200 KB Output is correct
8 Correct 82 ms 62200 KB Output is correct
9 Correct 82 ms 62204 KB Output is correct
10 Correct 86 ms 62332 KB Output is correct
11 Correct 84 ms 62200 KB Output is correct
12 Correct 82 ms 62200 KB Output is correct
13 Correct 84 ms 62280 KB Output is correct
14 Correct 81 ms 62200 KB Output is correct
15 Correct 80 ms 62200 KB Output is correct
16 Correct 85 ms 62200 KB Output is correct
17 Correct 82 ms 62204 KB Output is correct
18 Correct 84 ms 62200 KB Output is correct
19 Correct 82 ms 62284 KB Output is correct
20 Correct 85 ms 62444 KB Output is correct
21 Correct 88 ms 62200 KB Output is correct
22 Correct 89 ms 62200 KB Output is correct
23 Correct 86 ms 62200 KB Output is correct
24 Correct 82 ms 62200 KB Output is correct
25 Execution timed out 4102 ms 89208 KB Time limit exceeded
26 Halted 0 ms 0 KB -