oj.uz

답안 #1091941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091941 2024-09-22T16:26:37 Z underwaterkillerwhale Zoltan (COCI16_zoltan) C++17
140 / 140
 171 ms 19632 KB 
#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e16;
const ll BASE = 137;
const int szBL = 350;

inline void Add (int &A, int B) { A += B; if (A >= Mod) A -= Mod; }

struct Segment_Tree {
    int m;
    pii st[N << 2];

    void init (int n) {
        m = n;
    }

    pii mer (pii lc, pii rc) {
        if (lc.fs == rc.fs) return MP(lc.fs, (lc.se + rc.se) % Mod);
        else if (lc.fs > rc.fs) return lc;
        else return rc;
    }

    void update (int id, int l, int r, int pos, int u, int v) {
        if (l > pos|| r < pos) return;
        if (l == r) {
            if (st[id].fs < u) {
                st[id] = MP(u, v);
            }
            else if (st[id].fs == u) {
                Add(st[id].se, v);
            }
            return;
        }
        int mid = l + r >> 1;
        update (id << 1, l, mid, pos, u, v);
        update (id << 1 | 1, mid + 1, r, pos, u, v);
        st[id] = mer(st[id << 1], st[id << 1 | 1]);
    }

    pii get (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return MP(-1, 0);
        if (l >= u && r <= v) return st[id];
        int mid = l + r >> 1;
        return mer (get (id << 1, l, mid, u, v),
                    get (id << 1 | 1, mid + 1, r, u, v));
    }

    void update (int pos, int u, int v) {
        update (1, 0, m, pos, u, v);
    }

    pii get (int u, int v) {
        return get (1, 0, m, u, v);
    }
}ST, ST2;


int n;
int a[N];
pii dp[N], f[N];

void solution () {
    cin >> n;
    rep (i, 1, n) cin >> a[i];
    vector<int> vals;
    rep (i, 1, n) vals.pb(a[i]);
    sort (ALL(vals));
    vals.resize(unique(ALL(vals)) - vals.begin());
    rep (i, 1, n) a[i] = lower_bound(ALL(vals), a[i]) - vals.begin() + 1;
    ST.init(n + 1);
    ST.update(n + 1, 0, 1);
    ST2.init(n + 1);
    ST2.update(0, 0, 1);
    int LIS = 0;
    reb (i, n, 1) {
        dp[i] = ST.get(a[i] + 1, n + 1);
        dp[i].fs++;
        ST.update(a[i], dp[i].fs, dp[i].se);
        f[i] = ST2.get(0, a[i] - 1);
        f[i].fs++;
        ST2.update(a[i], f[i].fs, f[i].se);
        LIS = max(LIS, f[i].fs + dp[i].fs - 1);
    }
    cout << LIS <<" ";
    int res = 0;
    int delta = 1;
    rep (i, 1, n - LIS) delta = 2LL * delta % Mod;
    rep (i, 1, n) {
        if (f[i].fs + dp[i].fs - 1 == LIS) {
            Add(res, 1LL * f[i].se * dp[i].se % Mod);
        }
    }
    cout << 1LL * res * delta % Mod <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("DTREE");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug +9
*/

Compilation message

zoltan.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
zoltan.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = l + r >> 1;
      |                   ~~^~~
zoltan.cpp: In member function 'std::pair<int, int> Segment_Tree::get(int, int, int, int, int)':
zoltan.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 7 ms 12892 KB Output is correct
3 Correct 8 ms 12892 KB Output is correct
4 Correct 5 ms 12892 KB Output is correct
5 Correct 5 ms 12888 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 5 ms 12892 KB Output is correct
10 Correct 5 ms 13044 KB Output is correct
11 Correct 107 ms 17968 KB Output is correct
12 Correct 88 ms 17360 KB Output is correct
13 Correct 86 ms 17104 KB Output is correct
14 Correct 114 ms 17616 KB Output is correct
15 Correct 145 ms 18636 KB Output is correct
16 Correct 171 ms 19632 KB Output is correct
17 Correct 141 ms 18892 KB Output is correct
18 Correct 126 ms 18888 KB Output is correct
19 Correct 123 ms 19032 KB Output is correct
20 Correct 127 ms 19020 KB Output is correct