oj.uz

Submission #991274

# Submission time Handle Problem Language Result Execution time Memory
991274 2024-06-01T17:19:10 Z LOLOLO Zoltan (COCI16_zoltan) C++17
84 / 140
 274 ms 37204 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e5 + 10;
int a[N], mod = 1e9 + 7;

struct ST{
    vector <pair <int, ll>> seg;
    void ass(int n) {
        seg.assign(n * 4 + 100, {0, 0});
    }

    void upd(int id, int l, int r, int p, pair <int, ll> val) {
        if (l == r) {
            if (seg[id].f < val.f) {
                seg[id] = val;
            } else if (seg[id].f == val.f) {
                seg[id].s = (seg[id].s + val.s) % mod;
            }

            return;
        }

        int m = (l + r) / 2;
        if (m >= p) {
            upd(id * 2, l, m, p, val);
        } else {
            upd(id * 2 + 1, m + 1, r, p, val);
        }

        seg[id].f = max(seg[id * 2].f, seg[id * 2 + 1].f);
        if (seg[id * 2].f == seg[id * 2 + 1].f) {
            seg[id].s = (seg[id * 2].s + seg[id * 2 + 1].s) % mod;
        } else {
            seg[id].s = seg[id * 2].f > seg[id * 2 + 1].f ? seg[id * 2].s : seg[id * 2 + 1].s;
        }
    }

    pair <int, ll> get(int id, int l, int r, int u, int v) {
        if (l > v || r < u || u > v)
            return {0, 0};

        if (l >= u && r <= v)
            return seg[id];

        int m = (l + r) / 2;
        pair <int, ll> L = get(id * 2, l, m, u, v), R = get(id * 2 + 1, m + 1, r, u, v);
        if (L.f == R.f) {
            return {L.f, (L.s + R.s) % mod};
        } 

        return max(L, R);
    }
};

ll solve() {
    int n;
    cin >> n;

    int timer = 1;
    map <int, int> mp;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]];
    }

    for (auto &x : mp) {
        x.s = timer;
        timer++;
    }

    for (int i = 1; i <= n; i++) {
        a[i] = mp[a[i]];
    }

    ST lds, lis;
    lds.ass(n);
    lis.ass(n);

    pair <ll, ll> ans = {0, 0};

    for (int i = n; i >= 1; i--) {
        pair <ll, int> A = lds.get(1, 1, n, a[i] + 1, n), B = lis.get(1, 1, n, 1, a[i] - 1);
        A.f++, B.f++;
        if (A.s == 0)
            A.s++;

        if (B.s == 0)
            B.s++;

        pair <ll, ll> C = {A.f + B.f - 1, (A.s * B.s) % mod};
        if (ans.f < C.f) {
            ans = C;
        } else if (ans.f == C.f) {
            ans.s = (ans.s + C.s) % mod;
        }

        lds.upd(1, 1, n, a[i], A);
        lis.upd(1, 1, n, a[i], B);
    }

    ll tot = ans.s;
    for (int i = 1; i <= n - ans.f; i++) {
        tot = (tot + tot) % mod;
    }

    cout << ans.f << " " << tot << '\n';
    return 0;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
 
    int t = 1;
    //cin >> t;
 
    while (t--) {
        solve();
    }
 
    return 0;
}

Subtask #1
84.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 352 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Incorrect 1 ms 604 KB Output isn't correct
10 Correct 1 ms 488 KB Output is correct
11 Correct 158 ms 29496 KB Output is correct
12 Correct 133 ms 25428 KB Output is correct
13 Correct 123 ms 24092 KB Output is correct
14 Incorrect 177 ms 25936 KB Output isn't correct
15 Incorrect 230 ms 32168 KB Output isn't correct
16 Runtime error 274 ms 37204 KB Memory limit exceeded
17 Runtime error 175 ms 35160 KB Memory limit exceeded
18 Runtime error 171 ms 35152 KB Memory limit exceeded
19 Runtime error 180 ms 35152 KB Memory limit exceeded
20 Runtime error 168 ms 35404 KB Memory limit exceeded