oj.uz

Submission #991272

# Submission time Handle Problem Language Result Execution time Memory
991272 2024-06-01T17:17:30 Z LOLOLO Zoltan (COCI16_zoltan) C++17
84 / 140
 278 ms 37084 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++;

    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 1 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 1 ms 604 KB Output is correct
9 Incorrect 1 ms 604 KB Output isn't correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 145 ms 29344 KB Output is correct
12 Correct 135 ms 25428 KB Output is correct
13 Correct 129 ms 24148 KB Output is correct
14 Incorrect 156 ms 25940 KB Output isn't correct
15 Incorrect 224 ms 32088 KB Output isn't correct
16 Runtime error 278 ms 37084 KB Memory limit exceeded
17 Runtime error 155 ms 35416 KB Memory limit exceeded
18 Runtime error 165 ms 35380 KB Memory limit exceeded
19 Runtime error 177 ms 35412 KB Memory limit exceeded
20 Runtime error 165 ms 35196 KB Memory limit exceeded