oj.uz

답안 #988961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
988961 2024-05-27T04:55:46 Z Celebi_276 Zoltan (COCI16_zoltan) C++17
140 / 140
 111 ms 10068 KB 
#include <bits/stdc++.h>

using namespace std;

#define     exetime    cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
#define   ynifnl(c)    cout << ((c) ? "YES\n" : "NO\n")
#define     ynif(c)    cout << ((c) ? "YES" : "NO")
#define        TASK    "TEST"
#define        lint    long long int
#define       ulint    unsigned lint
#define       sz(v)    (int(v.size()))
#define      all(v)    v.begin(), v.end()
#define     rall(v)    v.rbegin(), v.rend()
#define          fi    first 
#define          se    second
#define     bit1(x)    __builtin_popcountll(x)
#define coutf(f, d)    cout << fixed << setprecision(d) << f

typedef pair <int, int> pii;
const int N = 2E5 + 25, MOD = 1E9 + 7;
int n, a[N], b[N];
pii R({0, 1}), G, lis[N], lds[N];

int mul (int a, int b) {
    int T = 0;
    for (; b; (a += a) %= MOD, b >>= 1) if (b & 1) (T += a) %= MOD;
    return T;
}
int pw2 (int a) {
    int T = 1;
    for (; a; --a, (T *= 2) %= MOD);
    return T;
}
void update_ (pii &A, pii B) {
    if (A.fi < B.fi) A = B;
    else if (A.fi == B.fi) (A.se += B.se) %= MOD;
}

namespace Fenwick_Tree {
    pii BIT[2][N];
    void update (bool t, int x, pii v) {
        if (!t) for (; x <= n; update_(BIT[t][x], v), x += x & -x);
        else for (; x; update_(BIT[t][x], v), x -= x & -x);
    }
    pii get (bool t, int x) {
        pii g = {0, 1};
        if (!t) for (; x; update_(g, BIT[t][x]), x -= x & -x);
        else for (; x <= n; update_(g, BIT[t][x]), x += x & -x);
        return g;
    }
}
using namespace Fenwick_Tree;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    if (fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    for (int i = n; i; --i) {
        lis[i] = get(1, a[i] + 1);
        lds[i] = get(0, a[i] - 1);
        lis[i].fi++;
        lds[i].fi++;
        G.fi = lis[i].fi + lds[i].fi - 1;
        G.se = mul(lis[i].se, lds[i].se);
        update_(R, G);
        update(1, a[i], lis[i]); update(0, a[i], lds[i]);
    }
    cout << R.fi << " " << mul(pw2(n - R.fi), R.se);
    return exetime, 0;
}

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4596 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 54 ms 8476 KB Output is correct
12 Correct 50 ms 7648 KB Output is correct
13 Correct 42 ms 8016 KB Output is correct
14 Correct 71 ms 8020 KB Output is correct
15 Correct 91 ms 9080 KB Output is correct
16 Correct 111 ms 10068 KB Output is correct
17 Correct 55 ms 9344 KB Output is correct
18 Correct 56 ms 9300 KB Output is correct
19 Correct 56 ms 9296 KB Output is correct
20 Correct 55 ms 9404 KB Output is correct