Submission #369657

#	Time	Username	Problem	Language	Result	Execution time	Memory
369657		Atill83	Zoltan (COCI16_zoltan)	C++14	140 / 140	498 ms	19432 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) 3e5+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 t1[4*MAXN], t2[4*MAXN];


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

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

        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, pii *t){
    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), t), b = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r, t);
        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, pii *t){
    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, t);
        else
            upd(2*v + 1, tm + 1, tr, pos, val, t);
        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;
}


int32_t 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]];
    }
    int ansLen = 0, ansCount = 0;

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


    build(1, 0, c - 1, t2);
    upd(1, 0, c - 1, 0, {0, 1}, t2);
    for(int i = n - 1; i >= 0; i--){
        pii gt1 = que(1, 1, c, a[i] + 1, c, t1), gt2 = que(1, 0, c - 1, 0, a[i] - 1, t2);
        //cerr<<i<<" "<<endl;
        //cerr<<gt1.ff<<" "<<gt1.ss<<endl<<gt2.ff<<" "<<gt2.ss<<endl;
        
        int nL = gt1.ff + gt2.ff + 1;
        int nC = 1LL * gt1.ss * gt2.ss % mod * bp(2, (n - 1) - nL + 1) % mod;

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

        gt1.ff++;
        gt2.ff++;
        upd(1, 1, c, a[i], gt1, t1);
        upd(1, 0, c - 1, a[i], gt2, t2);
    }
    

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



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

• Subtask 1: 140 / 140