Submission #369131

#	Time	Username	Problem	Language	Result	Execution time	Memory
369131		Atill83	Zoltan (COCI16_zoltan)	C++14	42 / 140	543 ms	17000 KiB

zoltan

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 2e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
int a[MAXN];
map<int, int> mp;
int c = 1;
pii t[4*MAXN];


void build(int v, int tl, int tr){
    if(tl == tr){
        t[v] = {0, 0};
    }else{
        int tm = (tl + tr) / 2;

        build(2*v, tl, tm);
        build(2*v + 1, tm + 1, tr);

        if(t[2*v].ff == t[2*v + 1].ff)
            t[v].ff = t[2*v].ff, t[v].ss = (t[2*v].ss + t[2*v + 1].ss) % mod;
        else
            t[v] = max(t[2*v], t[2*v + 1]);
    }
}

pii que(int v, int tl, int tr, int l, int r){
    if(l > r)
        return {0, 0};
    else if(l == tl && r == tr)
        return t[v];
    else{
        int tm = (tl + tr) / 2;
        pii a = que(2*v, tl, tm, l, min(tm, r)), b = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r);
        if(a.ff == b.ff)
            return {a.ff, (a.ss + b.ss) % mod};
        else
            return max(a, b);
    }
}

void upd(int v, int tl, int tr, int pos, pii val){
    if(tl == tr){
        if(t[v].ff == val.ff)
            t[v].ss = (t[v].ss + val.ss) % mod;
        else if(t[v].ff < val.ff)
            t[v] = val;
    }else{
        int tm = (tl + tr) / 2;
        if(pos <= tm)
            upd(2*v, tl, tm, pos, val);
        else
            upd(2*v + 1, tm + 1, tr, pos, val);
        if(t[2*v].ff == t[2*v + 1].ff)
            t[v].ff = t[2*v].ff, t[v].ss = (t[2*v].ss + t[2*v + 1].ss) % mod;
        else
            t[v] = max(t[2*v], t[2*v + 1]);
    }
}

int bp(int tab, int b){
    int res = 1;
    while(b){
        if(b % 2) res = 1LL * res * tab % mod;
        tab = 1LL * tab * tab % mod;
        b = b / 2;
    }
    return res;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif


    cin>>n;
    vector<int> comp;
    
    for(int i = 0; i < n; i++){
        cin>>a[i];
        comp.push_back(a[i]);
    }

    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());


    for(int i: comp)
        mp[i] = c++;

    for(int i = 0; i < n; i++)
        a[i] = mp[a[i]];

    build(1, 1, c);
    upd(1, 1, c, c, {0, 1});

    for(int i = n - 1; i > 0; i--){
        pii gt = que(1, 1, c, a[i] + 1, c);
        gt.ff++;
        upd(1, 1, c, a[i], gt);
    }
    

    vector<pii> frst(c + 1);
    frst[c] = {0, 1};
    for(int i = c - 1; i >= 1; i--){
        frst[i] = que(1, 1, c, i, i);
        if(frst[i].ff == frst[i + 1].ff)
            frst[i].ss = (frst[i].ss + frst[i + 1].ss) % mod;
    }


    build(1, 0, c - 1);
    upd(1, 0, c - 1, 0, {0, 1});

    for(int i = n - 1; i > 0; i--){
        pii gt = que(1, 0, c - 1, 0, a[i] - 1);
        gt.ff++;
        upd(1, 0, c - 1, a[i], gt);
    }


    int ansLen = 0, ansCount = 0;

    for(int i = 0; i < c; i++){
        pii dg = que(1, 0, c - 1, i, i);
        //cerr<<i<<endl;
        //cerr<<dg.ff<<" "<<dg.ss<<endl<<frst[i + 1].ff<<" "<<frst[i + 1].ss<<endl;
        int nL = dg.ff + frst[i + 1].ff,
            nC = 1LL * frst[i + 1].ss * dg.ss % mod * bp(2, n - 1 - nL) % mod;
        if(nL > ansLen){
            ansLen = nL;
            ansCount = nC;
        }else if(nL == ansLen)
            ansCount = (ansCount + nC) % mod;
    }
    //cerr<<ansLen<<" "<<ansCount<<endl;

    pii alt = que(1, 0, c - 1, 0, a[0] - 1), ust = frst[a[0] + 1];

    int nL = alt.ff + ust.ff + 1, nC = 1LL * alt.ss * ust.ss % mod * bp(2, n - nL) % mod;
    //cerr<<nL<<" "<<nC<<endl;

    if(nL > ansLen){
        ansLen = nL;
        ansCount = nC;
    }else if(nL == ansLen)
        ansCount = (ansCount + nC) % mod;


    cout<<ansLen<<" "<<ansCount<<endl;





    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

• Subtask 1: 42 / 140