Submission #254879

#	Time	Username	Problem	Language	Result	Execution time	Memory
254879		MarcoMeijer	Fibonacci representations (CEOI18_fib)	C++14	65 / 100	4086 ms	103016 KiB

fib

#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }

//===================//
//  Added libraries  //
//===================//

// mod library
ll MOD=1e9+7;

inline ll mod(ll x_) {
    return (x_)%MOD;
}
ll modpow(ll x_, ll N_) {
    if(N_ == 0) return 1;
    ll a = modpow(x_,N_/2);
    a = (a*a)%MOD;
    if(N_%2) a = (a*x_)%MOD;
    return a;
}
ll inv(ll x_) {
    return modpow(x_, MOD-2);
}
class mi {
public:
    mi(ll v=0) {value = v;}
    mi  operator+ (ll rs) {return mod(value+rs);}
    mi  operator- (ll rs) {return mod(value-rs+MOD);}
    mi  operator* (ll rs) {return mod(value*rs);}
    mi  operator/ (ll rs) {return mod(value*inv(rs));}
    mi& operator+=(ll rs) {*this = (*this)+rs; return *this;}
    mi& operator-=(ll rs) {*this = (*this)-rs; return *this;}
    mi& operator*=(ll rs) {*this = (*this)*rs; return *this;}
    mi& operator/=(ll rs) {*this = (*this)/rs; return *this;}
    operator ll&() {return value;}

    ll value;
};
typedef vector<mi> vmi;

//===================//
//end added libraries//
//===================//

void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}


//===================//
//   begin program   //
//===================//

const int MX = 5e5;
int n, a[MX];
map<int, int> mp;
set<int> ones;
set<int> inq, inpq;
queue<int> q;
priority_queue<int> pq;
int p[MX], m;
mi dp[MX][2];
bool findingPositions = 1;
set<int> positions;
int P[MX], N;
map<int, int> segUpdate;

struct M {
    mi m[2][2];
    mi* operator [] (int i) {return m[i];}
    M operator* (M& rhs) {
        M ans;
        RE(i,2) RE(j,2) RE(k,2) ans[i][j] += m[i][k]*rhs[k][j];
        return ans;
    }
};
struct S {
    int bg, ed;
    M m;
    S(int p = -1) {
        bg = p, ed = p;
        m[0][0] = 1;
        m[1][1] = 1;
        m[0][1] = 0;
        m[1][0] = 0;
    }
    S(S& l, S& r) {
        if(l.bg == -1) {
            *this = r;
            return;
        }
        if(r.bg == -1) {
            *this = l;
            return;
        }
        int dist = r.bg-l.ed;
        M mid;
        bg = l.bg;
        ed = r.ed;
        if((dist%2) == 0) {
            mid.m[0][0] = 1;
            mid.m[0][1] = 1;
        }
        mid.m[1][0] = mi((dist-1)/2);
        mid.m[1][1] = mi((dist-1)/2 + 1);

        m = (l.m * mid) * r.m;
    }
};

S SEG[MX*4];
int Low(int x) {
    return lower_bound(P,P+N,x)-P;
}
void setSeg(int i, int v, int p=0, int l=0, int r=N-1) {
    if(i < l || i > r) return;
    if(l == r) {
        SEG[p] = S(v);
        return;
    }
    int m=(l+r)/2;
    setSeg(i,v,p*2+1,l,m);
    setSeg(i,v,p*2+2,m+1,r);
    SEG[p] = S(SEG[p*2+1], SEG[p*2+2]);
}

void remove(int x) {
    mp.erase(x);
    if(!findingPositions) segUpdate[Low(x)] = -1;
}
void update(int x) {
    auto& am = mp[x];
    if(am == 0) remove(x);
    if(am == 1) ones.insert(x);
    else ones.erase(x);

    if(am >= 2) {
        if(inq.count(x)) return;
        q.push(x);
        inq.insert(x);
    } else if(am == 1) {
        if(inpq.count(x)) return;
        if(findingPositions) positions.insert(x);
        else segUpdate[Low(x)] = x;
        if(mp.count(x-1) && mp[x-1] == 1) {
            pq.push(x);
            inpq.insert(x);
        }
        if(mp.count(x+1) && mp[x+1] == 1) {
            pq.push(x+1);
            inpq.insert(x+1);
        }
    }
}
void fix(int x) {
    auto& am = mp[x];
    if(am >= 2) {
        int times = am/2;
        if(am%2) mp[x] = 1;
        else remove(x);
        if(x >= 3) {
            mp[x-2] += times;
            mp[x+1] += times;
            update(x-2);
            update(x+1);
        }
        if(x == 2) {
            mp[1] += times;
            mp[3] += times;
            update(1);
            update(3);
        }
        if(x == 1) {
            mp[2] += times;
            update(2);
        }
        update(x);
    }
}
void fix1(int x) {
    int am = ones.count(x);
    if(am == 1 && ones.count(x-1)) {
        mp[x-1]--;
        mp[x]--;
        mp[x+1]++;
        update(x-1);
        update(x);
        update(x+1);
    }
}

void program() {
    IN(n);
    RE(i,n) IN(a[i]);

    RE(i,n) {
        mp[a[i]]++;
        update(a[i]);
        while(!q.empty()) {
            int p = q.front(); q.pop();
            fix(p);
            inq.erase(p);
        }
        while(!pq.empty()) {
            int p = pq.top(); pq.pop();
            fix1(p);
            inpq.erase(p);
        }
    }
    
    N = 0;
    FOR(i,positions) P[N++] = i;

    findingPositions = 0;
    mp.clear();

    RE(i,n) {
        mp[a[i]]++;
        update(a[i]);
        while(!q.empty()) {
            int p = q.front(); q.pop();
            fix(p);
            inq.erase(p);
        }
        while(!pq.empty()) {
            int p = pq.top(); pq.pop();
            fix1(p);
            inpq.erase(p);
        }

        FOR(it,segUpdate) {
            setSeg(it.first, it.se);
        }
        segUpdate.clear();

        S ans(0);
        ans = S(ans,SEG[0]);
        OUTL(ll(ans.m[1][1]));
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 0 / 35