| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 70650 |
2018-08-23T08:08:19 Z |
노영훈(#2185) |
Toys (CEOI18_toy) |
C++11 |
|
13 ms |
8700 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, MOD=1e9+7, inf=2e9;
int n, A[MX];
void solve12(){
__int128 F[151], val=0;
int one[151];
int D[151], E[151]; // stay, down
F[1]=1, F[2]=2;
for(int i=3; i<=150; i++) F[i]=F[i-1]+F[i-2];
for(int j=1; j<=n; j++){
val+=F[A[j]];
__int128 now=val;
for(int i=1; i<=150; i++) one[i]=D[i]=E[i]=0;
for(int i=150; i>=1; i--)
if(F[i]<=now) now-=F[i], one[i]=1;
D[0]=1, E[0]=0;
ll ans=0;
for(int i=1, j=0; i<=150; i++){
if(!one[i]) continue;
D[i] = (D[j] + E[j]) % MOD;
E[i] = (ll(i-j-1)/2 * D[j] + ll(i-j)/2 * E[j]) % MOD;
ans=(D[i]+E[i])%MOD;
j=i;
}
cout<<ans<<'\n';
}
}
void solve3(){
vector<int> pos={0};
int D[101], E[101]; // stay, down
for(int j=1; j<=n; j++){
pos.push_back(A[j]);
sort(pos.begin(), pos.end());
D[0]=1, E[0]=0;
for(int i=1; i<(int)pos.size(); i++) D[i]=E[i]=0;
int ans=0;
for(int i=1; i<(int)pos.size(); i++){
D[i] = (D[i-1] + E[i-1]) % MOD;
E[i] = (ll(pos[i]-pos[i-1]-1)/2 * D[i-1] + ll(pos[i]-pos[i-1])/2 * E[i-1]) % MOD;
ans = (D[i]+E[i])%MOD;
}
cout<<ans<<'\n';
}
}
void norm(map<int, int> &cnt){
vector<int> V;
for(pii p:cnt)
if(p.second==0) V.push_back(p.first);
for(int x:V) cnt.erase(x);
}
void check2(map<int, int> &cnt){
int rig=-1, lft=-1;
for(pii p:cnt) if(p.second==2) rig=p.first;
if(rig<0) return;
if(rig==1){
cnt.erase(1); cnt[2]=1; return;
}
if(rig==2){
cnt.erase(2); cnt[1]=cnt[3]=1; return;
}
for(int i=rig, tmp=0; i>=0; i--){
if(cnt[i]==0) tmp++;
else tmp=0;
if(tmp==2){ lft=i; break; }
}
assert(lft>0);
for(int i=lft; i<=rig; i++) cnt.erase(i);
cnt[lft]=1;
for(int i=lft+3; i<=rig+1; i+=2) cnt[i]=1;
}
void check11(map<int, int> &cnt){
int lft=-1, rig=-1;
for(auto it=next(cnt.begin()); it!=cnt.end(); it++)
if(prev(it)->first == it->first-1) lft = prev(it)->first;
if(lft<0) return;
for(int i=lft, tmp=0; i<=inf; i++){
if(cnt[i]==0) tmp++;
else tmp=0;
if(tmp==2){ rig=i; break; }
}
for(int i=lft; i<=rig; i++) cnt.erase(i);
cnt[rig-1]=1;
}
void check(map<int, int> &cnt){
norm(cnt);
check2(cnt);
norm(cnt);
check11(cnt);
norm(cnt);
}
void solve4(){
map<int, int> cnt;
int D[151], E[151];
for(int i=1; i<=n; i++){
cnt[A[i]]++;
cnt.erase(0);
check(cnt);
cnt[0]=1;
D[0]=1, E[0]=0;
for(int i=1; i<=150; i++) D[i]=E[i]=0;
int ans=0, pos=1;
for(auto it=next(cnt.begin()); it!=cnt.end(); it++, pos++){
int i=it->first, j=prev(it)->first;
D[pos] = (D[pos-1] + E[pos-1]) % MOD;
E[pos] = (ll(i-j-1)/2 * D[pos-1] + ll(i-j)/2 * E[pos-1]) % MOD;
ans = (D[pos]+E[pos])%MOD;
}
cout<<ans<<'\n';
}
}
struct mat22{
int A[2][2]={1,0,0,1};
mat22(){}
mat22(int c, int d){
A[0][0]=1, A[0][1]=1, A[1][0]=c, A[1][1]=d;
}
mat22 operator * (const mat22 m) const {
mat22 res;
for(int i=0; i<2; i++) for(int j=0; j<2; j++) res.A[i][j]=0;
for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++)
res.A[i][j]+=1LL*A[i][k]*m.A[k][j]%MOD;
for(int i=0; i<2; i++) for(int j=0; j<2; j++) res.A[i][j]%=MOD;
return res;
}
void show(){
cout<<A[0][0]<<' '<<A[0][1]<<'\n'<<A[1][0]<<' '<<A[1][1]<<'\n';
}
} tree[1<<18];
void upt(int v, int s, int e, int x, mat22 &m){
if(x<s || e<x) return;
if(s==e){
tree[v]=m; return;
}
upt(v*2,s,(s+e)/2,x,m);
upt(v*2+1,(s+e)/2+1,e,x,m);
tree[v]=tree[v*2+1]*tree[v*2];
}
void upt(int pos, mat22 m){
upt(1,1,n,pos,m);
}
int get(){
return (tree[1].A[0][0]+tree[1].A[1][0])%MOD;
}
void solve5(){
vector<int> X={0};
for(int i=1; i<=n; i++) X.push_back(A[i]);
set<int> S; S.insert(0);
sort(X.begin(), X.end());
for(int i=1; i<=n; i++){
int a=A[i], pos=lower_bound(X.begin(), X.end(), a)-X.begin();
auto it=S.lower_bound(a);
int z=a-*prev(it)-1;
upt(pos, mat22(z/2, (z+1)/2));
if(it!=S.end()){
int b=*it, sop=lower_bound(X.begin(), X.end(), b)-X.begin();
int w=b-a-1;
upt(sop, mat22(w/2, (w+1)/2));
}
S.insert(a);
cout<<get()<<'\n';
}
}
int main(){
assert(false);
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
int mx=0;
for(int i=1; i<=n; i++) cin>>A[i], mx=max(mx, A[i]);
if(n<=100){
solve4();
return 0;
// if(mx<=100) solve12();
// else solve3();
// return 0;
}
else{
solve5();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
8700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
8700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
8700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
8700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
8700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
