oj.uz

Submission #1037141

# Submission time Handle Problem Language Result Execution time Memory
1037141 2024-07-28T08:46:58 Z BF001 Zoltan (COCI16_zoltan) C++17
49 / 140
 153 ms 24004 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define N 200005
#define fi first
#define se second

typedef pair<int, int> ii;

int md = 1e9 + 7;
 
struct fw{
    int n;
    vector<ii> bit;

    fw(int siz){
        n = siz;
        bit.resize(n + 1, {0, 0});
    }

    void add(ii& a, ii b){
        if (a.fi == b.fi){
            a.se = (a.se + b.se) % md;
        }
        else if (a.fi < b.fi) a.se = b.se;
        a.fi = max(a.fi, b.fi);
    }

    void ud1(int pos, ii val){
        while (pos <= n){
            add(bit[pos], val);
            pos += (pos & (-pos));
        }
    }

    ii get1(int pos){
        ii rt = {0, 1};
        while (pos >= 1){
            add(rt, bit[pos]);
            pos -= (pos & (-pos));
        }
        return rt;
    }

    void ud2(int pos, ii val){
        while (pos >= 1){
            add(bit[pos], val);
            pos -= (pos & (-pos));
        }
    }

    ii get2(int pos){
        ii rt = {0, 1};
        while (pos <= n){
            add(rt, bit[pos]);
            pos += (pos & (-pos));
        }
        return rt;
    }

};

void add(ii& a, ii b){
    if (a.fi == b.fi){
        a.se = (a.se + b.se) % md;
    }
    else if (a.fi < b.fi) a.se = b.se;
    a.fi = max(a.fi, b.fi);
}

int pw(int a, int n){
    int rt = 1;
    while (n){
        if (n & 1) rt = rt * a % md;
        a = a * a % md;
        n >>= 1;
    }
    return rt;
}

int n, a[N];
vector<int> cy;
map<int, int> dd;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        cy.push_back(a[i]);
    }

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

    int pos = 0;
    for (auto x : cy) dd[x] = ++pos;
    for (int i = 1; i <= n; i++){
        a[i] = dd[a[i]];
    }
    
    fw s1(pos), s2(pos);
    ii res = {0, 0};

    for (int i = n; i >= 1; i--){
        ii dp1 = s1.get1(a[i] - 1);
        ii dp2 = s2.get2(a[i] + 1);
        add(res, {dp1.fi + dp2.fi + 1, dp1.se * dp2.se % md});
        s1.ud1(a[i], {dp1.fi + 1, dp2.se});
        s2.ud2(a[i], {dp2.fi + 1, dp2.se});
    }

    cout << res.fi << " " << (res.se * pw(2, n - res.fi)) % md;

    return 0;
}

Subtask #1
49.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Correct 88 ms 18848 KB Output is correct
12 Correct 73 ms 16328 KB Output is correct
13 Correct 78 ms 15404 KB Output is correct
14 Incorrect 97 ms 16836 KB Output isn't correct
15 Incorrect 125 ms 20680 KB Output isn't correct
16 Incorrect 153 ms 24004 KB Output isn't correct
17 Incorrect 102 ms 20400 KB Output isn't correct
18 Incorrect 98 ms 20424 KB Output isn't correct
19 Incorrect 93 ms 20472 KB Output isn't correct
20 Incorrect 109 ms 20424 KB Output isn't correct