Submission #577250

#	Time	Username	Problem	Language	Result	Execution time	Memory
577250		Ronin13	Zoltan (COCI16_zoltan)	C++14	112 / 140	354 ms	31468 KiB

zoltan

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const ll mod = 1e9 + 7;

map <int, int> mp;
const int NMAX = 2e5 + 5;

pll t[4 * NMAX][2];

pll combine(pll a, pll  b){
    if(a.f == b.f) return {a.f, (a.s + b.s) % mod};
    if(a.f > b.f) return a;
    return b;
}

int n;

void build(int v, int l, int r){
    if(l == r){
        if(l == n + 2) {
            t[v][0].s = 1;
        }
        if(l == 1){
            t[v][1].s = 1;
        }
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v][0] = combine(t[2 * v][0], t[2 * v + 1][0]);
    t[v][1] = combine(t[2 * v][1], t[2 * v + 1][1]);
}

pll get(int v, int l, int r, int st, int fin, int ind){
    if(l > fin || r < st) return {-1, -1};
    if(l >= st && r <= fin) return t[v][ind];
    int m = (l + r) / 2;
    pll x = get(2 * v, l, m, st, fin, ind);
    pll y = get(2 * v + 1, m + 1, r, st, fin, ind);
    return combine(x, y);
}


void update(int v, int l, int r, int pos, pll val, int ind){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v][ind] = val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val, ind);
    update(2 * v + 1, m + 1, r, pos, val, ind);
    t[v][ind] = combine(t[2 * v][ind], t[2 * v + 1][ind]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    int a[n + 1];
    pii b[n + 1];
    for(int i = 1; i <= n ; i++){
        cin >> a[i];
        b[i] = {a[i], i};
    }
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i++){
        mp[b[i].f] = i + 1;
    }
    for(int i = 1; i <= n; i++){
        a[i] = mp[a[i]];
    }
    build(1, 1, n + 2);
    pll ans[n + 1];
    ll mx = 0;
    ll cnt = 0;
    for(int i = n; i >= 1; i--){
        pll x = get(1, 1, n + 2, 1, a[i] - 1, 1);
        pll y = get(1, 1, n + 2, a[i] + 1, n + 2, 0);
        ans[i] = {x.f + y.f + 1, x.s * y.s % mod};
        update(1, 1, n + 2, a[i], {x.f + 1, x.s}, 1);
        update(1, 1, n + 2, a[i], {y.f + 1, y.s}, 0);
        mx = max(mx, ans[i].f);
    }
    for(int i = 1; i <= n; i++){
        if(mx == ans[i].f){
            cnt += ans[i].s;
            cnt %= mod;
        }
    }
    for(int i = 1; i <= n - mx; i++){
        cnt *= 2;
        cnt %= mod;
    }
    cout << mx << ' ' << cnt << "\n";
    return 0;
}

• Subtask 1: 112 / 140