Submission #98540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98540	2019-02-23T22:06:02 Z	dalgerok	Zoltan (COCI16_zoltan)	C++17	140 / 140	311 ms	9452 KB

zoltan

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



const int N = 2e5 + 5, MOD = 1e9 + 7;




int n, m, a[N];
pair < int, int > b[N], c[N], t[4 * N];



vector < int > e;
inline int Find(int x){
    return lower_bound(e.begin(), e.end(), x) - e.begin() + 1;
}


void build(int v, int l, int r){
    t[v] = make_pair(-1, -1);
    if(l == r){
        return;
    }
    int mid = (r + l) >> 1;
    build(v + v, l, mid);
    build(v + v + 1, mid + 1, r);
}

inline pair < int, int > comb(pair < int, int > a, pair < int, int > b){
    if(a.first == -1){
        return b;
    }
    if(b.first == -1){
        return a;
    }
    int mx = max(a.first, b.first);
    int cur = 0;
    if(mx == a.first){
        cur += a.second;
        if(cur >= MOD){
            cur -= MOD;
        }
    }
    if(mx == b.first){
        cur += b.second;
        if(cur >= MOD){
            cur -= MOD;
        }
    }
    return make_pair(mx, cur);
}

pair < int, int > get(int v, int l, int r, int tl, int tr){
    if(l > r || l > tr || tl > r || tl > tr){
        return make_pair(-1, -1);
    }
    if(tl <= l && r <= tr){
        return t[v];
    }
    int mid = (r + l) >> 1;
    return comb(get(v + v, l, mid, tl, tr), get(v + v + 1, mid + 1, r, tl, tr));
}

void update(int v, int l, int r, int pos, pair < int, int > val){
    if(l == r){
        t[v] = comb(t[v], val);
        return;
    }
    int mid = (r + l) >> 1;
    if(pos <= mid){
        update(v + v, l, mid, pos, val);
    }
    else{
        update(v + v + 1, mid + 1, r, pos, val);
    }
    t[v] = comb(t[v + v], t[v + v + 1]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        e.push_back(a[i]);
    }
    sort(e.begin(), e.end());
    e.resize(unique(e.begin(), e.end()) - e.begin());
    m = (int)e.size();
    for(int i = 1; i <= n; i++){
        a[i] = Find(a[i]);
    }
    build(1, 1, n);
    for(int i = n; i >= 1; i--){
        auto it = get(1, 1, m, 1, a[i] - 1);
        if(it.first == -1){
            it.first = 0;
            it.second = 1;
        }
        it.first += 1;
        b[i] = it;
        update(1, 1, m, a[i], it);
    }
    build(1, 1, n);
    for(int i = n; i >= 1; i--){
        auto it = get(1, 1, m, a[i] + 1, m);
        if(it.first == -1){
            it.first = 0;
            it.second = 1;
        }
        it.first += 1;
        c[i] = it;
        update(1, 1, m, a[i], it);
    }
    pair < int, int > kek = make_pair(-1, -1);
    for(int i = 1; i <= n; i++){
        kek = comb(kek, make_pair(b[i].first - 1 + c[i].first, 1LL * b[i].second * c[i].second % MOD));
    }
    for(int i = 1; i <= n - kek.first; i++){
        kek.second = 2LL * kek.second % MOD;
    }
    cout << kek.first << " " << kek.second;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	384 KB	Output is correct
11	Correct	183 ms	8300 KB	Output is correct
12	Correct	168 ms	7880 KB	Output is correct
13	Correct	127 ms	5572 KB	Output is correct
14	Correct	189 ms	7888 KB	Output is correct
15	Correct	259 ms	8680 KB	Output is correct
16	Correct	311 ms	9420 KB	Output is correct
17	Correct	217 ms	9452 KB	Output is correct
18	Correct	215 ms	9324 KB	Output is correct
19	Correct	270 ms	9452 KB	Output is correct
20	Correct	237 ms	9372 KB	Output is correct